More Web Proxy on the site http://driver.im/

research-article

The Evolution of Search: Three Computing Paradigms

Authors:

Minghui WuAuthors Info & Claims

ACM Transactions on Management Information Systems (TMIS), Volume 13, Issue 2

Article No.: 20, Pages 1 - 20

https://doi.org/10.1145/3495214

Published: 10 March 2022 Publication History

Abstract

Search is probably the most common activity that humans conduct all the time. A search target can be a concrete item (with a yes or no answer and location information), an abstract concept (such as the most important information on the Web about Xindong Wu), or a plan/path for a specific target with an objective function (like flight scheduling with a minimal travel time), among others. In this article, we propose a Universal Connection Theorem (UCT) to suggest that all physical objects/items in the universe are connected through explicit or implicit relationships. Search is to explore the relationships, using different computing methods, to retrieve relevant objects. Under the UCT theorem, we summarize mainstream search approaches into two categories from the user perspective, deterministic search vs. abstract search, and further distinguish them into three computing paradigms: planning based search, data driven search, and knowledge enhanced search. The planning based paradigm explores search as a planning process in a large search space, by graph traversing with heuristic principles to locate optimal solutions. The data driven paradigm seeks to find objects matching the user's query from a large data repository. Indexing, hashing, information retrieval, and recommendations are typical strategies to tackle the data volumes and select the best answers for users’ queries. The knowledge enhanced search does not aim to find matching objects, but to discover and then meet user's search requirements through knowledge mining. The evolution of these three search paradigms, from planning to data engineering and knowledge engineering, provides increasing levels of challenges and opportunities. This article elaborates the respective principles of these paradigms.

References

[1]

R. E. Korf. 1988. Search: A Survey of Recent Results, Exploring Artificial Intelligence. Morgan kaufmann Publisher Inc. 197–237

[2]

R. Levionson, F.-H. Hsu, J. Schaeffer, T. A. Marsland, and D. E. Wilkins. 1991. The role of chees in artificial intelligence research. In Proceedings of the 12th International Joint Conference on Artificial Intelligence. 547–552.

[3]

B. Bouzy and T. Cazenave. 2001. Computer Go: An AI oriented survey. Artificial Intelligence 132, 1 (2001), 39–103.

Digital Library

[4]

S. Brin and L. Page. 1998. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the International Conference on World Wide Web. 107–117.

Digital Library

[5]

X. Dong, E. Gabrilovich, G. Heitz, W. Horn, N. Lao, K. Murphy, T. Strohmann, S. Sun, and W. Zhang. 2014. Knowledge vault: A web-scale approach to probabilistic knowledge fusion. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[6]

J. Pujara, H. Miao, L. Getoor, and W. Cohen. 2013. Knowledge graph identification. In Proceedings of the International Semantic Web Conference.

Digital Library

[7]

R. L. Rivest. 1988. Game tree searching by min/max approximation. Artificial Intelligence 34, 1 (1988), 77–96.

Digital Library

[8]

P. Hart, N. Nilsson, and B. Raphael. 1968. A formal basis for the heuristic determination of minimal cost paths. IEEE Transactions on Systems Science and Cybernetics 4, 2 (1968), 100–107.

[9]

P. Felzenszwald and D. McAllester. 2007. The generalized a* architecture. Journal of Artificial Intelligence Research 29, (2007), 153–190.

[10]

K. Shvachko, H. Kuang, S. Radia, and R. Chansler. 2010. The hadoop distributed file system. In Proceedings of the 26^th IEEE Symposium on Mass Storage Systems and Technologies. 1–10.

Digital Library

[11]

D. Comer. 1979. The Ubiquitous B-Tree. ACM Computing Survey 11, 2 (1979), 121–57.

Digital Library

[12]

J. L. Bentley. 1975. Multidimensional binary search trees used for associative search. Communications of the ACM 18, 9 (1975), 509–517.

Digital Library

[13]

A. Guttman. 1984. R-Tree: A dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 47–57.

Digital Library

[14]

M. Fontoura, V. Josifovski, J. Liu, S. Venkatesan, X. Zhu, and J. Zien. 2011. Evaluation strategies for top-k queries over memory resident inverted indexes. In Proceedings of the VLDB Endowment 4, 12 (2011), 1213–1224.

Digital Library

[15]

P. Melville and V. Sindhwani. 2011. Recommender Systems. In Encyclopedia of Machine Learning, C. Sammut, G. I. Webb (Eds.). Springer, Boston, MA. 2011.

[16]

H. Ma, D. Zhou, C. Liu, M. Lyu, and I. King. 2011. Recommender systems with social regularization. In Proceedings of the 4th ACM International Conference on Web Search and Data Mining.

Digital Library

[17]

D. Ferrucci, A. Levas, S. Bagchi, D. Gondek, and E. Mueller. 2013. Watson: Beyond Jeopardy!. Artificial Intelligence 199–200 (2013), 93–105.

[18]

A. Singhal. Introducing the Knowledge Graph: Things, not Strings, Official Blog (of Google). Retrieved 22 Nov., 2020 from http://googleblog.blogspot.com/2012/05/introducing-knowledge-graph-things-not.html.

[19]

B. Bonet and H. Geffner. 2001. Planning as heuristic search. Artificial Intelligence 129, 1–2 (2001), 5–33.

Digital Library

[20]

B. Sarwar, G. Karypis, J. Konstan, and J. Riedl. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the International Conference on World Wide Web. 285–295.

Digital Library

[21]

J. Wang, A. P. Vries, and M. Reinders. 2006. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In Proceedings of the 29^th ACM SIGIR Conference. 501–508.

Digital Library

[22]

S. Mukherjea, B. Bamba, and P. Kankar. 2003. Information retrieval and knowledge discovery utilizing a biomedical patent semantic Web. IEEE Transactions on Knowledge and Data Engineering 17, 8 (2003), 1099–1110.

Digital Library

[23]

C. Y. Lee. 1961. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers EC–10, 3 (1961), 346–365.

[24]

R. Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM Journal of Computer 1, 2 (1972), 146–160.

Digital Library

[25]

D. E. Knuth and R. W. Moore. 1975. An analysis of alpha-beta pruning. Artificial Intelligence 6, 4 (1975), 293–326.

[26]

R. Bisiani. 1987. Beam search. In Proceedings of the Encyclopedia of Artificial Intelligence. S. Shapiro (Ed.). 56–58. Wiley & Sons.

[27]

E. Alba and J. Troya. 1998. A survey of parallel distributed genetic algorithms. Reseaux et Systems Repartis 10, 2 (1988), 141–171.

[28]

M. Zinkevich, M. Weimer, L. Li, and A. Smola. 2010. Parallelized stochastic gradient descent. In Proceedings of the Advances in Neural Information Processing Systems 2010.

[29]

P. Ciaccia, M. Patella, and P. Zezula. 1997. M-tree: An efficient access method for similarity search in metric space. In Proceedings of the 23^rd VLDB Conference. 426–435.

[30]

B. Bloom. 1970. Space/time trade-offs in hashing coding with allowable errors. Communications of the ACM 13, 7 (1970), 422–426.

Digital Library

[31]

P. Indyk, R. Motwani, P. Raghavan, and S. Vempala. 1997. Locality-preserving hashing in multidimensional spaces. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 618–625.

Digital Library

[32]

H. Lejsek, F. Asmundsson, B. Jonsson, and L. Amsaleg. 2009. NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections. IEEE Transactions on PAMI 31, 5 (2009), 869–883.

Digital Library

[33]

S. Robsertson. 2004. Understanding inverse document frequency: On theoretical arguments for IDF. Journal of Documentation 60, 5 (2004), 503–520.

[34]

L. Page, S. Brin, R. Motwani, and T. Winograd. 1999. The pagerank citation ranking: Bringing order to the web. Technical Report. Stanford InfoLab 1999.

[35]

M. Evans. 2007. Analysing google rankings through search engine optimization data. Internet Research 17, 1 (2007), 21–37.

[36]

R. Li, B. Li, C. Jin, X. Xue, and X. Zhu. 2011. Tracking user-preference varying speed in collaborative filtering. In Proceedings of the 25th AAAI Conference on Artificial Intelligence.

[37]

B. Li, X. Zhu, R. Li, and C. Zhang. 2015. Rating knowledge sharing in cross-domain collaborative filtering. IEEE Transactions on Cybernetics 45, 5 (2015), 1054–1068.

[38]

I. Rigoutsos and A. Floratos. 1998. Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm. Bioinformatics 14, 1 (1988), 55–67.

[39]

X. Yan and J. Han. 2002. gSpan: Graph-based substructure pattern mining. In Proceedings of the IEEE International Conference on Data Mining.

Digital Library

[40]

T. L. Bailey, M. Boden, F. A. Buske, M. Frith, C. E. Grant, L. Clementi, J. Ren, W. W. Li, and W. S. Noble. 2009. MEME Suite: Tools for motif discovery and searching. Nucleic Acids Research 39, Suppl_2 (2009), W202–W208.

[41]

X. Zhu and X. Wu. 2007. Mining complex patterns across sequences with gap requirements. In Proceedings of the International Joint Conference on Artificial Intelligence. 2934–2941.

[42]

Y. Wu, Y. Tong, X. Zhu, and X. Wu. 2018. NOSEP: Nonoverlapping sequence pattern mining with gap constraints. IEEE Transactions On Cybernetics 48, 10 (2018), 2809–2822.

[43]

L. B. Alexandrov, Serena Nik-Zainal, David C. Wedge, Samuel Aparicio, Sam Behjati, Andrew Biankin, Graham R. Bignell, Niccolò Bolli, Ake Borg, Anne-Lise Børresen-Dale, Sandrine Boyault, Birgit Burkhardt, Adam Butler, Carlos Caldas, Helen Davies, Christine Desmedt, Roland Eils, Jorunn Erla Eyfjörd, John A. Foekens, Mel Greaves, Fumie Hosoda, Barbara Hutter, Tomislav Ilicic, Sandrine Imbeaud, Marcin Imielinsk, Natalie Jäger, David T. W. Jones, David Jones, Stian Knappskog, Marcel Kool, Sr Lakhani, Carlos López-Otín, Sancha Martin, Nikhil C. Munshi, Hiromi Nakamura, Paul Northcott, Marina Pajic, Elli Papaemmanuil, Angelo Paradiso, John V. Pearson, Xose S. Puente, Keiran Martin Raine, Manasa Ramakrishna, Andrea L. Richardson, Julia Richter, Philip Rosenstiel, Matthias Schlesner, Ton N. Schumacher, Paul N. Span, Jon W. Teague, Yasushi Totoki, Andrew Tutt, Rafael Valdés-Mas, Marit van buuren, Laura J. van 't Veer, Anne Vincent-Salomon, Nicola Waddell, Lucy R. Yates, Jessica Zucman-Rossi, P. Andrew Futreal, Ultan Mcdermott, Peter Lichter, Matthew Meyerson, Sean Grimmond, Reiner Siebert, Elias Campo, Tatsuhiro Shibata, Stefan M. Pfister, Peter J. Campbell, and Michael R. Stratton. 2013. Signatures of mutational processes in human cancer. Nature 500, 7463 (2013), 415–421.

[44]

X. Zhu and X. Wu. 2007. Discovering relational patterns across multiple databases. In Proceedings of the IEEE ICDE Conference. 726–735.

[45]

M. Curtiss, Iain Becker, Tudor Bosman, Sergey Doroshenko, Lucian Grijincu, Tom Jackson, Sandhya Kunnatur, Soren Lassen, Philip Pronin, Sriram Sankar, Guanghao Shen, Gintaras Woss, Chao Yang, and Ning Zhang. 2013. Unicorn: A system for searching the social graph. In Proceedings of the VLDB Endowment 6, 11 (2013), 1150–1161.

Digital Library

[46]

X. Wu, T. Jiang, Y. Zhu, and C. Bu. 2020. Knowledge graph for china's genealogy. In Proceedings of the 11th IEEE International Conference on Knowledge Graph. 529–535.

[47]

L. Chi and X. Zhu. 2017. Hashing techniques: A survey and taxonomy. ACM Computing Survey 50, 1 (2017), 1–36.

Digital Library

[48]

S. Okura, Y. Tagami, S. Ono, and A. Tajima. 2017. Embedding-based news recommendation for millions of users. In Proceedings of the 23^rd ACK SIGKDD Conference 2017.

Digital Library

[49]

J. Huang, A. Sharma, S. Sun, L. Xia, D. Zhang, P. Pronin, J. Padmanabhan, G. Ottaviano, and L. Yang. 2020. Embedding-based retrieval in facebook search. In Proceedings of the 26th ACM SIGKDD Conference. 23–27.

Digital Library

[50]

D. Zhang, J. Yin, X. Zhu, and C. Zhang. 2021. Search efficient binary network embedding. ACM Transactions on Knowledge Discovery from Data 15, 4 (2021) 61, 1–27.

Digital Library

[51]

D. Domingo-Fernández, S. Baksi, B. Schultz, Yojana Gadiya, Reagon Karki, Tamara Raschka, Christian Ebeling, Martin Hofmann-Apitius, Alpha Tom Kodamullil. 2021. COVID-19 Knowledge graph: A computable, multi-modal, cause-and-effect knowledge model of COVID-19 pathophysiology. Bioinformatics 37, 9 (2021), 1332–1334.

[52]

H. Chen, X. Liu, D. Yin, and J. Tang. 2017. A survey on dialogue systems: Recent advances and new frontiers. ACM SIGKDD Explorations 19, 2 (2017), 25–35.

Digital Library

[53]

J. Gao, M. Galley, and L. Li. 2019. Neural approaches to conversational AI. Foundations and Trends in Information Retrieval 13, 2–3 ( 2019), 27–298.

[54]

Z. Zhao, M. Zhou, and S. Liu. 2021. Iterated greedy algorithms for flow-shop scheduling problems: A tutorial. IEEE Transactions on Automation Science and Engineering (2021), 1–19. DOI:, 2021.

[55]

Y. Yu, S. Gao, Y. Wang, and Y. Todo. 2019. Global optimum-based search differential evolution. IEEE/CAA Journal of Automatica Sinica 6, 2 (2019), 379–394.

[56]

X. Luo, W. Qin, A. Dong, K. Sedraoui, and M. Zhou. 2021. Efficient and high-quality recommendations via momentum-incorporated parallel stochastic gradient descent-based learning. IEEE/CAA Journal of Automatica Sinica 8, 2 (2011), 402–411.

[57]

M. E. Elkin, W. A. Andrews, and X. Zhu. 2019. Network analysis and recommendation for infectious disease clinical trial research. In Proceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics. 347–356.

Digital Library

[58]

John J. Kineman. 2011. Relational science: A synthesis. Axiomathes 21, 3 (2011), 393–437.

[59]

B. Hu, Z. Cao, and M. Zhou. 2021. An efficient RRT-based framework for planning short and smooth wheeled robot motion under kinodynamic constraints. IEEE Transactions on Industrial Electronics 68, 4 (2021), 3292–3302.

[60]

C. Bron. 1972. Merge sort algorithm. Communications of the ACM 15, 5 (1972), 357–358.

Digital Library

[61]

H. H. Seward. 1954. Information sorting in the application of electronic digital computers to business operations. Master's thesis. Report R-232, Massachusetts Institute of Technology, Digital Computer Laboratory. 25–28.

[62]

John Guare. 1990. Six Degrees of Separation: A Play (1st. ed.). New York: Random House. ISBN 0-679-40161-X.

[63]

J. Wang, Y. Sun, Z. Zhang, and S. Gao. 2020. Solving multitrip pickup and delivery problem with time windows and manpower planning using multiobjective algorithms. IEEE/CAA Journal of Automatica Sinica 7, 4 (2020), 1134–1153. DOI:

[64]

Junqing Li, Hongyan Sang, Quanke Pan, Peiyong Duan, and Kaizhou Gao. Solving multi-area environmental/economic dispatch by pareto-based chemical-reaction optimization algorithm. IEEE CAA Journal of Automatica Sinica 6, 5 (2019), 1240–1250.

[65]

X. Xu, J. Li, and M. Zhou. 2021. Delaunay-triangulation-based variable neighborhood search to solve large-scale general colored traveling salesman problems. IEEE Transactions on Intelligent Transportation Systems 22, 3 (2021), 1583–1593. DOI:

Digital Library

[66]

Z. Zhang, M. Zhou, and J. Wang. 2020. Construction-based optimization approaches to airline crew rostering problem. IEEE Transactions on Automation Science and Engineering 17, 3 (2020), 1399–1409. DOI:

[67]

J. Wang, M. Zhou, X. Guo, and L. Qi. 2019. Multiperiod asset allocation considering dynamic loss aversion behavior of investors. IEEE Transactions on Computational Social Systems 6, 1 (2019), 73–81. DOI:

Cited By

Wu YWang ZLi YGuo YJiang HZhu XWu X(2024)Co-occurrence Order-preserving Pattern Mining with Keypoint Alignment for Time SeriesACM Transactions on Management Information Systems10.1145/365845015:2(1-27)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1145/3658450
Ouyang WDong RTao RLiu XHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)FedUD: Exploiting Unaligned Data for Cross-Platform Federated Click-Through Rate PredictionProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657941(2416-2420)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657941
Geng MWu YLi YLiu JFournier-Viger PZhu XWu X(2024)RNP-Miner: Repetitive Nonoverlapping Sequential Pattern MiningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.333430036:9(4874-4889)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3334300
Show More Cited By

Index Terms

The Evolution of Search: Three Computing Paradigms
1. Computing methodologies
  1. Machine learning
    1. Machine learning algorithms
2. Information systems
  1. Data management systems
    1. Database management system engines
  2. Information retrieval
    1. Retrieval tasks and goals

Recommendations

Breadth-first heuristic search

Recent work shows that the memory requirements of A* and related graph-search algorithms can be reduced substantially by only storing nodes that are on or near the search frontier, using special techniques to prevent node regeneration, and recovering ...
Anytime search in dynamic graphs

Agents operating in the real world often have limited time available for planning their next actions. Producing optimal plans is infeasible in these scenarios. Instead, agents must be satisfied with the best plans they can generate within the time ...
Weighted A∗ search -- unifying view and application

The A^* algorithm is a well-known heuristic best-first search method. Several performance-accelerated extensions of the exact A^* approach are known. Interesting examples are approximate algorithms where the heuristic function used is inflated by a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Management Information Systems

ACM Transactions on Management Information Systems Volume 13, Issue 2

June 2022

261 pages

ISSN:2158-656X

EISSN:2158-6578

DOI:10.1145/3483345

Editor:
Daniel Zeng
Chinese Academy of Sciences, China

Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 March 2022

Accepted: 01 November 2021

Revised: 01 September 2021

Received: 01 January 2021

Published in TMIS Volume 13, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
398
Total Downloads

Downloads (Last 12 months)121
Downloads (Last 6 weeks)16

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu YWang ZLi YGuo YJiang HZhu XWu X(2024)Co-occurrence Order-preserving Pattern Mining with Keypoint Alignment for Time SeriesACM Transactions on Management Information Systems10.1145/365845015:2(1-27)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1145/3658450
Ouyang WDong RTao RLiu XHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)FedUD: Exploiting Unaligned Data for Cross-Platform Federated Click-Through Rate PredictionProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657941(2416-2420)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657941
Geng MWu YLi YLiu JFournier-Viger PZhu XWu X(2024)RNP-Miner: Repetitive Nonoverlapping Sequential Pattern MiningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.333430036:9(4874-4889)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3334300
Picalho AFadel LGonçalves A(2023)Expressões de busca e o uso de diferentes operadores avançados de pesquisa em um mecanismo de buscaTexto Livre10.1590/1983-3652.2023.4753116Online publication date: 2023
https://doi.org/10.1590/1983-3652.2023.47531
Wu YChen MLi YLiu JLi ZLi JWu X(2023)ONP-Miner: One-off Negative Sequential Pattern MiningACM Transactions on Knowledge Discovery from Data10.1145/354994017:3(1-24)Online publication date: 22-Feb-2023
https://dl.acm.org/doi/10.1145/3549940
Wu YMeng YLi YGuo LZhu XFournier-Viger PWu X(2023)COPP-Miner: Top-k Contrast Order-Preserving Pattern Mining for Time Series ClassificationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.332174936:6(2372-2387)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3321749
Li YZhang CLi JSong WQi ZWu YWu X(2023)MCoR-Miner: Maximal Co-Occurrence Nonoverlapping Sequential Rule MiningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.324121335:9(9531-9546)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3241213
Hu HZhang JXia RLiu S(2023)CCSMP: an efficient closed contiguous sequential pattern mining algorithm with a pattern relation graphApplied Intelligence10.1007/s10489-023-05118-x53:24(29723-29740)Online publication date: 3-Nov-2023
https://dl.acm.org/doi/10.1007/s10489-023-05118-x
Li YLiu JGuo YLiu JWu Y(2022)AOP-Miner: Approximate Order-Preserving Pattern Mining for Time Series2022 IEEE International Conference on Knowledge Graph (ICKG)10.1109/ICKG55886.2022.00026(149-156)Online publication date: Nov-2022
https://doi.org/10.1109/ICKG55886.2022.00026

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents