Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

This is an Open Access publication published under CSC-OpenAccess Policy.
Skip List: Implementation, Optimization and Web Search
Godwin Adu-Boateng, Matthew N. Anyanwu
Pages - 7 - 13     |    Revised - 30-06-2015     |    Published - 31-07-2015
Volume - 5   Issue - 1    |    Publication Date - July 2015  Table of Contents
Skip List, Efficient Algorithms, Web Search.
Even as computer processing speeds have become faster and the size of memory has also increased over the years, the need for elegant algorithms (programs that accomplish such tasks/operations as information retrieval, and manipulation as efficiently as possible) remain as important now as it did in the past. It is even more so as more complex problems come to the fore. Skip List is a probabilistic data structure with algorithms to efficiently accomplish such operations as search, insert and delete. In this paper, we present the results of implementing the Skip List data structure. The paper also addresses current Web search strategies and algorithms and how the application of Skip List implementation techniques and extensions can bring about optimal search query results.
CITED BY (0)  
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Scribd
5 slideshare
6 PdfSR
1 C.A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis – Java Edition. Prentice-Hall, Inc., pp. 365-371, 1998.
2 Z.Galil and G.F. Italiano. Data Structures and Algorithms for Disjoint Set Union Problems. ACM Computing Surveys vol. 23, pp. 319-344.
3 M.A. Weiss, Data Structures and Algorithm Analysis in C++, Benjamin/Cummings, Redwood City, Calif., Chap 8, pp. 287, 1994.
4 W.J. Collins. Data Structures and the Java Collections Framework. McGraw Hill. pp. 389 – 432, 2002.
5 A.V. Aho, J.E. Hopcroft, J.Ullman. Data Structures and Algorithms. Addison-Wesley Longman Publishing Co., 1983.
6 T. Kanungo, D.M. Mount, N.S. Netanyahu, C. Piatko, R. Silverman, A.Y. Wu. “An Efficient kMeans Clustering Algorithm: Analysis and Implementation.” IEEE Trans. Patt. Anal. Mach. Intell, v. 24, no.7, pp. 881-892, 2002.
7 A. Levintin. Introduction to the Design & Analysis of Algorithms. Addison-Wesley, 2006.
8 J. Porter. Designing for the social web. Peachpit Press, 2010.
9 H.R. Varian. The economics of Internet search. University of California at Berkeley, 2006.
10 D.A. Grossman. Information retrieval: Algorithms and heuristics. Vol. 15. Springer, 2004.
11 M. Gordon and P. Pathak. “Finding information on the World Wide Web: The retrieval effectiveness of search engines.” Information Processing and Management, 35(2), pp. 141– 180, 1999.
12 H. Cao, A.Bhardwaj and V. Govindaraju. “A probabilistic method for keyword retrieval in handwritten document images.” Pattern Recognition, 42(12), pp. 3374-3382, 2009.
13 S. Lohr. (2012). “The Age of Big Data.” The New York Times. Retrieved Jan 2013, available online: http://www.nytimes.com/2012/02/12/sunday-review/big-datas-impact-in-theworld.html?_r=2&scp=1&sq=Big%20Data&st=cse&.
14 A. McAfee and E. Brynjolfsson. “Big data: the management revolution.” Harvard Business Review, 90(10), pp. 60-66, 2012.
15 R. Delbru, S. Campinas and G. Tummarello. Searching web data: An entity retrieval and high-performance indexing model. Web Semantics: Science, Services and Agents on the World Wide Web, 10, pp. 33-58.
16 W. Pugh. “Skip Lists: A Probabilistic alternative to balanced trees.” Communications of the ACM, v. 33. pp. 668-676, 1990.
17 W. Pugh. “A skip list cookbook.” University of Maryland, Department of Computer Science Report CS-TR-2286.1, 1989.
18 J. Gabarro, C. Martinez and X. Messeguer. “A design of a parallel dictionary using skip lists.” Theoretical Computer Science 158, pp. 1-33, 1996.
19 F. Keir. Practical lock-freedom. Diss. University of Cambridge, 2004.
20 T. Ge and S. Zdonik. “A Skip-list approach for efficiently processing forecasting queries.” Proceedings of the VLDB Endowment 1.1, pp. 984-995, 2008.
21 J. El-Sana, E. Azanli, and A. VARSHNEY. Skip Strips: Maintaining Triangle Strips for View- Dependent Rendering. In IEEE Visualization ’99 Proceedings, pp. 131–138, 1999.
22 J. Li, B.T. Loo, J. M. Hellerstein, M. F. Kaashoek, D. R. Karger, and R. Morris. “On the feasibility of peer-to-peer web indexing and search.” In Peer-to-Peer Systems II. Springer Berlin Heidelberg. pp. 207-215, 2003.
23 L.A. Barroso, J. Dean, and U. Holzle. "Web search for a planet: The Google cluster architecture." Micro, IEEE 23.2, pp. 22-28, 2003.
24 P. Boldi and V. Sebastiano. "Compressed perfect embedded skip lists for quick invertedindex lookups." String Processing and Information Retrieval. Springer Berlin Heidelberg, 2005.
25 F. Chierichetti, R. Kumar and P. Raghavan. "Compressed web indexes." Proceedings of the 18th international conference on World Wide Web. ACM, 2009.
26 S. Campinas, R. Delbru, and G. Tummarello. "SkipBlock: self-indexing for block-based inverted list." Advances in Information Retrieval. Springer Berlin Heidelberg, pp. 555-561, 2011.
Mr. Godwin Adu-Boateng
Center of Biostatistics and Bioinformatics Department of Medicine University of Mississippi Medical Center Jackson, MS 39216, USA - United Stated of America
Dr. Matthew N. Anyanwu
- United States of America