Information retrieval from data sets of maximal value via analogue neural circuit identification from signal set

2013;
: pp. 16 – 20
Authors: 
Tymoshchuk P.

L’viv Polytechnic National University, CAD Department

Using the analogue neural circuit of maximal value signals from signal set identification is proposed for information retrieval in data sets. The circuit is fast, it has simple structure and can be implemented in a modern hardware. A resolution of the circuit is theoretically infinite and it is not dependent on a value of its parameter. An average time necessary for trajectory convergence of the circuit state variable to a steady state is not dependent on a dimension of input data. The results of numerical experiments obtained on the base of the data set provided by PageRank algorithm are presented. These results give witness of the circuit using for information search in data sets.

1. S. Lawrence and C. L. Giles, “Acc essibility o f i nformation on the web,” Nature, vo l. 400, pp. 107– 109, 1 999. 2. S. Brin, and L. Page, “The anatomy of a large-scale hypertextual web se arch engine,” in Proceedings o f 7th International W orld Wide Web Confere nce, 1998. 3. L. Page , S. Br in, R. Motwani, and T. Winograd, “The PageRank citation ranking: bringing order to the web,” Technical report, S tanford Un iversity, 1998. 4. T. H. Ha veliwala, “Eff icient compu tation of PageR ank,” S tanford Univ. Technical Report, 1999. 5. T. H. Haveliwa la and S. Kamvar, “The se cond eigenvalue of the google matrix,” St anford Un iv. Technical Repor t, 20 03. 6. A. Arasu, J. Nova k, J. Tomlin, and J. Tom lin, “PageRank compu tation and th e s tructure o f the we b: e xperiments a nd a lgorithms,” in Proc eedings o f 11th International World Wide Web Conferen ce, pp. 107–11 7, 20 02. 7 . G. M. Del Cor so, A . Gul l, and F. Romani, “Fast PageRank computation via a sparse linear system,” Internet Mathematics, vol. 2, no. 3, pp. 251–273, 2005. 8. S. Kamvar, T. Haveliwala, C. Manning, and G. Golub, “Extrapolation methods for accelerating PageRank computations,” in Proceedings of 12th International World Wide Web Conference 2003. 9. A. Mislove, M. Marcon, K. P. Gummad i, P. Druschel, and B. Bhattacharjee, “Measurement and analysis of on line so cial networks,” in P roceedings of 7th ACM S IGCOMM Conference on Internet Measurement, pp. 29–42, 2007. 10. J. T ang, J. Sun, C. Wang, and Z. Yang, “Social influence analysis in large-scale netwo rks,” i n Procee dings of 15t h In ternational Con ference on K nowledge Disco very and Data Mining, 2009. 11. G. N. Freder ickson and D. B . Johnson, “Generalized selection and r anking,” in Proc. of the 12 th STOC, pp. 420–428, 1980. 12. M. Kenda ll an d J. D. Gi bbons, “Ran k cor relation methods,” Edward Arnold, London, 1990. 13. R. Fagi n, R. Kumar, and D. Sivakumar, “Comparing top-k lists,” SIA M J. Dis crete Math, vo l. 17, pp. 1 34–160, 2003. 14. N. Mamoulis, M. Yiu, K. Ch eng, and D. W. Cheung, “Ef ficient top-k aggregation of ranked inputs,” ACM Transactions on Database Systems, vol. 32, no. 3, article 19, 2007. 15. P. Hall and M. G. Schinek, “Inference for the top-k rank list problem,” in Proce edings in Compu tational St atistics, pp. 433 –444, 2008. 16. K. Hende rson and T. Elia ssi-Rad, “Solving the top-k problem with fixed-memory heuristic search,” Technical report, Lawrence Livermore National L aboratory, 2 009. 17. Z. Guo and J. W ang, “In formation r etrieval from la rge data se ts v ia multiple-winners-take-all”, in : Pro c. ISCAS, 2011, pp. 2669 –2672. 18. T. M. Kwon and M. Zer vakls, “KWTA networks and their applications,” Multidimensional Syst. Signal Process., vol. 6, n o. 4, pp. 333 – 346, 1995. 19. J. W ang, “Analysis and design of an analog sorting network,” IEEE Trans. Neural Netw., vol. 6, no. 4, pp. 962–971, Jul. 1995. 20. Wang, J.: Analysis and design of a k-winners-take-all model with a si ngle s tate va riable an d t he Heav iside step ac tivation f unction. I EEE T rans. on Ne ural Ne tworks 9, 1496-1506 (2010). 21. E. Majani, R. Erlanson and Y. Abu-Mostafa, “On the k-winners-take-all network,” Advances in Neural Information Processing Systems, vol. 1, pp. 634–642, 1989. 22. W . Maass, “On the computational power of winner-take-all,” Neural Comput., vol. 12, pp. 2519–2535, 2000. 23. R. Erlanson and Y. Abu-Mostafa, “Analog neural networks as decoders,” Advances in Neural Information Processing Systems, vol. 1, pp. 585– 588, 1991. 24. A. Y uille and D. Geiger, “W inner-take-all ne tworks,” The Handbook of Brain Th eory and Neural Ne tworks (2nd ed.), MIT Pre ss Cambridge, MA, pp. 12 28–1231, 2003. 25. A. Fi sh, D. Aks elrod, and O. Y adid-Pecht, “High precision image centroid computation via an adaptive k -winner-take-all ci rcuit in co njunction wi th a dynamic elem ent mat ching a lgorithm fo r sta r tracking app lications,” An alog Integrated C ircuits a nd Sign al P rocessing, v ol. 39, pp. 2 51–266, 2004 . 26. A. K. J. Hertz, and R. G. Palmer, “In troduction to the Theory of Neural Computation,” Redwood City, CA: Add ison-Wesley, 199 1. 27. Тимощук П.В. Модель аналогової нейронної схеми ідентифікації найбільших сигналів // Комп’ютерні системи та мережі. – 2012. – № 745. – С. 180–185. (Вісн. Нац. ун-ту "Львівська політехніка"). 28. T he Google Search Engine: Commercial search engine founded by the originators of PageRank. Located at http://www.google.com/. 29. Z. Guo and J. W ang, “Information retrieval from large data sets via multiple-winners-take-all”, in: Proc. ISCAS, 2011, pp. 2669–2672.