Home   >   CSC-OpenAccess Library   >    Manuscript Information
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
MORE INFORMATION
KEYWORDS
Skip List, Efficient Algorithms, Web Search.
ABSTRACT
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.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
A. Levintin. Introduction to the Design & Analysis of Algorithms. Addison-Wesley, 2006.
A. McAfee and E. Brynjolfsson. “Big data: the management revolution.” Harvard Business Review, 90(10), pp. 60-66, 2012.
A.V. Aho, J.E. Hopcroft, J.Ullman. Data Structures and Algorithms. Addison-Wesley Longman Publishing Co., 1983.
C.A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis – Java Edition. Prentice-Hall, Inc., pp. 365-371, 1998.
D.A. Grossman. Information retrieval: Algorithms and heuristics. Vol. 15. Springer, 2004.
F. Chierichetti, R. Kumar and P. Raghavan. "Compressed web indexes." Proceedings of the 18th international conference on World Wide Web. ACM, 2009.
F. Keir. Practical lock-freedom. Diss. University of Cambridge, 2004.
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.
H.R. Varian. The economics of Internet search. University of California at Berkeley, 2006.
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.
J. Gabarro, C. Martinez and X. Messeguer. “A design of a parallel dictionary using skip lists.” Theoretical Computer Science 158, pp. 1-33, 1996.
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.
J. Porter. Designing for the social web. Peachpit Press, 2010.
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.
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.
M.A. Weiss, Data Structures and Algorithm Analysis in C++, Benjamin/Cummings, Redwood City, Calif., Chap 8, pp. 287, 1994.
P. Boldi and V. Sebastiano. "Compressed perfect embedded skip lists for quick invertedindex lookups." String Processing and Information Retrieval. Springer Berlin Heidelberg, 2005.
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.
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.
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&.
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.
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.
W. Pugh. “A skip list cookbook.” University of Maryland, Department of Computer Science Report CS-TR-2286.1, 1989.
W. Pugh. “Skip Lists: A Probabilistic alternative to balanced trees.” Communications of the ACM, v. 33. pp. 668-676, 1990.
W.J. Collins. Data Structures and the Java Collections Framework. McGraw Hill. pp. 389 – 432, 2002.
Z.Galil and G.F. Italiano. Data Structures and Algorithms for Disjoint Set Union Problems. ACM Computing Surveys vol. 23, pp. 319-344.
Mr. Godwin Adu-Boateng
Center of Biostatistics and Bioinformatics Department of Medicine University of Mississippi Medical Center Jackson, MS 39216, USA - United States of America
gaduboateng@umc.edu
Dr. Matthew N. Anyanwu
- United States of America