Abstract
Output-sensitive data structures result from preprocessing n items and are capable of reporting the items satisfying an on-line query in O(t(n) + ℓ) time, where t(n) is the cost of traversing the structure and ℓ ≤ n is the number of reported items satisfying the query. In this paper we focus on rank-sensitive data structures, which are additionally given a ranking of the n items, so that just the top k best-ranking items should be reported at query time, sorted in rank order, at a cost of O(t(n) + k) time. Note that k is part of the query as a parameter under the control of the user (as opposed to ℓ which is query-dependent). We explore the problem of adding rank-sensitivity to data structures such as suffix trees or range trees, where the ℓ items satisfying the query form O(polylog(n)) intervals of consecutive entries from which we choose the top k best-ranking ones. Letting s(n) be the number of items (including their copies) stored in the original data structures, we increase the space by an additional term of O(s(n) lgε n) memory words of space, each of O(lg n) bits, for any positive constant ε < 1. We allow for changing the ranking on the fly during the lifetime of the data structures, with ranking values in 0 ... O(n). In this case, query time becomes O(t(n) + k) plus O(lg n/ lg lg n) per interval; each change in the ranking and each insertion/deletion of an item takes O(lg n); the additional term in space occupancy increases to O(s(n) lg n/ lg lg n).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ajtai, M., Fredman, M., Komlòs, J.: Hash functions for priority queues. Information and Control 63(3), 217–225 (1984)
Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM Journal on Computing 32, 1488–1508 (2003)
Baeza-Yates, R.A., Ribeiro-Neto, B.: Modern Information Retrieval. Addison-Wesley Longman Publishing Co., Inc., Amsterdam (1999)
Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing 17(3), 427–462 (1988)
de Berg, M., van Kreveld, M., Overmars, M., Schwartzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Heidelberg (1997)
Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Computer and System Sciences 38(1), 86–124 (1989)
Ferragina, P., Grossi, R.: The string B-tree: A new data structure for string search in external memory and its applications. J. ACM 46, 236–280 (1999)
Fiat, A., Kaplan, H.: Making data structures confluently persistent. J. Algorithms 48(1), 16–58 (2003)
Fich, F.E.: Class notes CSC 2429F: Dynamic data structures. Department of Computer Science. University of Toronto, Canada (2003)
Frederickson, G.N.: An optimal algorithm for selection in a min-heap. Inf. Comput. 104(2), 197–214 (1993)
Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. JCSS 48(3), 533–551 (1994)
Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: STOC 1984, Washington, D.C, pp. 135–143 (1984)
Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997)
Hearn, D., Baker, M.: Computer Graphics with OpenGL. Prentice-Hall, Englewood Cliffs (2003)
Kaplan, H., Molad, E., Tarjan, R.E.: Dynamic rectangular intersection with priorities. In: STOC 2003, pp. 639–648. ACM Press, New York (2003)
Kitsios, N., Makris, C., Sioutas, S., Tsakalidis, A., Tsaknakis, J., Vassiliadis, B.: 2-D spatial indexing scheme in optimal time. In: Masunaga, Y., Thalheim, B., Štuller, J., Pokorný, J. (eds.) ADBIS 2000 and DASFAA 2000. LNCS, vol. 1884, p. 107. Springer, Heidelberg (2000)
Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. Journal of the ACM 46(5), 604–632 (1999)
Lempel, R., Moran, S.: SALSA: the stochastic approach for link-structure analysis. ACM Transactions on Information Systems 19(2), 131–160 (2001)
McCreight, E.M.: Priority search trees. SIAM Journal on Computing 14(2), 257–276 (1985)
Mortensen, C.W.: Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. In: SODA 2003, pp. 618–627 (2003)
Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA 2002: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, pp. 657–666 (2002)
Myrvold, W., Ruskey, F.: Ranking and unranking permutations in linear time. Information Processing Letters 79(6), 281–284 (2001)
Overmars, M.H.: The Design of Dynamic Data Structures. LNCS, vol. 156. Springer, Heidelberg (1983)
Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Tech. rep, Stanford University, Stanford, CA (1998)
Raman, R.: Eliminating amortization: on data structures with guaranteed response time. PhD thesis, Rochester, NY, USA (1993)
Thorup, M.: On AC0 implementations of fusion trees and atomic heaps. In: Proceedings of the fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), January 12–14, pp. 699–707. ACM Press, New York (2003)
Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14, 249–260 (1995)
Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Computing Surveys 33(2), 209–271 (2001)
Vuillemin, J.: A unifying look at data structures. Communications of the ACM 23(4), 229–239 (1980)
Weiner, P.: Linear pattern matching algorithms. In: Conference Record, IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 1–11 (1973)
Ian Witten, H., Moffat, A., Bell, T.C.: Managing gigabytes: Compressing and indexing documents and images. Morgan Kaufmann Pubs. Inc., San Francisco (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bialynicka-Birula, I., Grossi, R. (2005). Rank-Sensitive Data Structures. In: Consens, M., Navarro, G. (eds) String Processing and Information Retrieval. SPIRE 2005. Lecture Notes in Computer Science, vol 3772. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11575832_10
Download citation
DOI: https://doi.org/10.1007/11575832_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29740-6
Online ISBN: 978-3-540-32241-2
eBook Packages: Computer ScienceComputer Science (R0)