{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T08:18:48Z","timestamp":1771661928584,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1994,7,1]],"date-time":"1994-07-01T00:00:00Z","timestamp":773020800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1994,7,1]],"date-time":"1994-07-01T00:00:00Z","timestamp":773020800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1994,7]]},"DOI":"10.1007\/bf02574372","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:11:43Z","timestamp":1174565503000},"page":"151-175","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Search costs in quadtrees and singularity perturbation asymptotics"],"prefix":"10.1007","volume":"12","author":[{"given":"P.","family":"Flajolet","sequence":"first","affiliation":[]},{"given":"T.","family":"Lafforgue","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,9,6]]},"reference":[{"key":"BF02574372_CR1","unstructured":"M. Abramowitz and I. A. Stegun.Handbook of Mathematical Functions. Dover, 1973. A reprint of the tenth National Bureau of Standards edition, 1964."},{"key":"BF02574372_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0097-3165(73)90038-1","volume":"15","author":"E. A. Bender","year":"1973","unstructured":"E. A. Bender. Central and local limit theorems applied to asymptotic enumeration.Journal of Combinatorial Theory, 15:91\u2013111, 1973.","journal-title":"Journal of Combinatorial Theory"},{"key":"BF02574372_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-55251-0_2","volume-title":"CAAP \u201992","author":"F. Bergeron","year":"1992","unstructured":"F. Bergeron, P. Flajolet, and B. Salvy. Varieties of increasing trees. In J.-C. Raoult, editor,CAAP \u201992, pages 24\u201348 (Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, France, February 1992). Lecture Notes in Computer Science, Volume 581. Springer-Verlag, Berlin, 1992."},{"key":"BF02574372_CR4","volume-title":"Probability and Measure","author":"P. Billingsley","year":"1986","unstructured":"P. Billingsley.Probability and Measure, 2nd edition, Wiley, New York, 1986.","edition":"2nd edition"},{"issue":"1","key":"BF02574372_CR5","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1287\/moor.9.1.43","volume":"9","author":"G. G. Brown","year":"1984","unstructured":"G. G. Brown and B. O. Shubert. On random binary trees.Mathematics of Operations Research, 9(1):43\u201365, 1984.","journal-title":"Mathematics of Operations Research"},{"key":"BF02574372_CR6","volume-title":"Theory of Ordinary Differential Equations","author":"E. A. Coddington","year":"1955","unstructured":"E. A. Coddington and M. Levinson,Theory of Ordinary Differential Equations. McGraw-Hill, New York, 1955."},{"key":"BF02574372_CR7","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1137\/0219057","volume":"19","author":"L. Devroye","year":"1990","unstructured":"L. Devroye and L. Laforest, An analysis of randomd-dimensional quad trees.SIAM Journal on Computing, 19:821\u2013832, 1990.","journal-title":"SIAM Journal on Computing"},{"key":"BF02574372_CR8","unstructured":"M. Drmota. Asymptotic distributions and a multivariate Darboux method in enumeration problems. Manuscript, 1990."},{"key":"BF02574372_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R. A. Finkel","year":"1974","unstructured":"R. A. Finkel and J. L. Bentley. Quad trees, a data structure for retrieval on composite keys.Acta Informatica, 4:1\u20139, 1974.","journal-title":"Acta Informatica"},{"key":"BF02574372_CR10","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/BF01891833","volume":"10","author":"P. Flajolet","year":"1993","unstructured":"P. Flajolet, G. Gonnet, C. Puech, and J. M. Robson. Analytic variation on quadtrees.Algorithmica, 10:473\u2013500, 1993.","journal-title":"Algorithmica"},{"issue":"2","key":"BF02574372_CR11","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0403019","volume":"3","author":"P. Flajolet","year":"1990","unstructured":"P. Flajolet and A. M. Odlyzko. Singularity analysis of generating functions.SIAM Journal on Discrete Mathematics, 3(2):216\u2013240, 1990.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"BF02574372_CR12","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1145\/5383.5453","volume":"22","author":"P. Flajolet","year":"1986","unstructured":"P. Flajolet and C. Puech. Partial match retrieval of multidimensional data.,Journal of the ACM, 22(2):371\u2013407, 1986.","journal-title":"Journal of the ACM"},{"key":"BF02574372_CR13","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0097-3165(90)90056-3","volume":"53","author":"P. Flajolet","year":"1990","unstructured":"P. Flajolet and M. Soria. Gaussian limiting distributions for the number of components in combinatorial structures.Journal of Combinatorial Theory, Series A, 53:165\u2013182, 1990.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"BF02574372_CR14","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0012-365X(93)90364-Y","volume":"114","author":"P. Flajolet","year":"1993","unstructured":"P. Flajolet and M. Soria. General combinatorial schemas: Gaussian limit distributions and exponential tails.Discrete Mathematics, 114:159\u2013180, 1993.","journal-title":"Discrete Mathematics"},{"issue":"12","key":"BF02574372_CR15","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1051\/ita\/197610R300351","volume":"10","author":"J. Fran\u00e7on","year":"1976","unstructured":"J. Fran\u00e7on. Arbres binaires de recherche: Propri\u00e9t\u00e9s combinatoires et applications.RAIRO Informatique Th\u00e9orique, 10(12):35\u201350, 1976.","journal-title":"RAIRO Informatique Th\u00e9orique"},{"key":"BF02574372_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0304-3975(77)90034-2","volume":"4","author":"J. Fran\u00e7on","year":"1977","unstructured":"J. Fran\u00e7on. On the analysis of algorithms for trees.Theoretical Computer Science, 4:155\u2013169, 1977.","journal-title":"Theoretical Computer Science"},{"key":"BF02574372_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0377-0427(92)90247-U","volume":"41","author":"Z. Gao","year":"1992","unstructured":"Z. Gao and L. B. Richmond. Central and local limit theorems applied to asymptotic enumerations, IV: Multivariate generating functions.Journal of Computational and Applied Mathematics, 41:177\u2013186, 1992.","journal-title":"Journal of Computational and Applied Mathematics"},{"key":"BF02574372_CR18","volume-title":"Handbook of Algorithms and Data Structures: in Pascal and C","author":"G. H. Gonnet","year":"1991","unstructured":"G. H. Gonnet and R. Baeza-Yates,Handbook of Algorithms and Data Structures: in Pascal and C, 2nd edition. Addison-Wesley. Reading, MA, 1991.","edition":"2nd edition"},{"key":"BF02574372_CR19","volume-title":"Applied and Computational Complex Analysis","author":"P. Henrici","year":"1977","unstructured":"P. Henrici.Applied and Computational Complex Analysis, 3 volumes. Wiley, New York, 1977."},{"key":"BF02574372_CR20","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/BF02074876","volume":"32","author":"M. Hoshi","year":"1992","unstructured":"M. Hoshi and P. Flajolet. Page usage in a quadtree index.BIT, 32:384\u2013402, 1992.","journal-title":"BIT"},{"key":"BF02574372_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/BFb0022669","volume-title":"CAAP \u201986","author":"P. Jacquet","year":"1986","unstructured":"P. Jacquet and M. R\u00e9gnier. Trie partitioning process: Limiting distributions. In P. Franchi-Zanetacchi, editor,CAAP \u201986 pages 196\u2013210 (Proceedings of the 11th Colloquium on Trees in Algebra and Programming, Nice France, March 1986). Lecture Notes in Computer Science, Volume 214. Springer-Verlag, Berlin, 1986."},{"key":"BF02574372_CR22","volume-title":"The Art of Computer Programming","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth,The Art of Computer Programming, Volume 3. Addison-Wesley, Reading, MA, 1973."},{"key":"BF02574372_CR23","series-title":"Technical Report 3","volume-title":"\u00c9tude des arbres hyperquaternaires","author":"L. Laforest","year":"1990","unstructured":"L. Laforest, \u00c9tude des arbres hyperquaternaires. Technical Report 3, LACIM, UQAM, Montreal, Nov. 1990. (Author\u2019s Ph.D. Thesis at McGill University.)"},{"issue":"4","key":"BF02574372_CR24","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1051\/ita\/1987210404791","volume":"21","author":"G. Louchard","year":"1987","unstructured":"G. Louchard. Exact and asymptotic distributions in digital and binary search trees,RAIRO Theoretical Informatics and Applications, 21(4):479\u2013495, 1987.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"BF02574372_CR25","volume-title":"Characteristic Functions","author":"E. Lukacs","year":"1970","unstructured":"E. Lukacs.Characteristic Functions. Griffin, London, 1970."},{"key":"BF02574372_CR26","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1093\/comjnl\/7.4.299","volume":"7","author":"W. L. Lynch","year":"1965","unstructured":"W. L. Lynch. More combinatorial problems on certain trees.Computer Journal, 7:299\u2013302, 1965.","journal-title":"Computer Journal"},{"key":"BF02574372_CR27","volume-title":"Evolution of Random Search Trees","author":"H. Mahmoud","year":"1992","unstructured":"H. Mahmoud.Evolution of Random Search Trees. Wiley, New York, 1992."},{"key":"BF02574372_CR28","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/0196-6774(89)90023-0","volume":"10","author":"H. M. Mahmoud","year":"1989","unstructured":"H. M. Mahmoud and B. Pittel. Analysis of the space of search trees under the random insertion algorithm.Journal of Algorithms, 10:52\u201375, 1989.","journal-title":"Journal of Algorithms"},{"key":"BF02574372_CR29","volume-title":"Applications of Spatial Data Structures","author":"H. Samet","year":"1990","unstructured":"H. Samet.Applications of Spatial Data Structures. Addition-Wesley, Reading, MA, 1990."},{"key":"BF02574372_CR30","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H. Samet","year":"1990","unstructured":"H. Samet.The Design and Analysis of Spatial Data Structures. Addison-Wesley, MA, 1990."},{"key":"BF02574372_CR31","volume-title":"Algorithms","author":"R. Sedgewick","year":"1988","unstructured":"R. Sedgewick.Algorithms, 2nd edition. Addison-Wesley, Reading, MA, 1988.","edition":"2nd edition"},{"key":"BF02574372_CR32","unstructured":"W. Wasow.Asymptotic Expansions for Ordinary Differential Equations. Dover, 1987. A reprint of the Wiley edition, 1965."},{"key":"BF02574372_CR33","volume-title":"A Course of Modern Analysis","author":"E. T. Whittaker","year":"1927","unstructured":"E. T. Whittaker and G. N. Watson.A Course of Modern Analysis, 4th edition. Cambridge University Press, Cambridge, 1927. Reprint 1973.","edition":"4th edition"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574372.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02574372\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574372.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T07:11:19Z","timestamp":1713424279000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02574372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,7]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,7]]}},"alternative-id":["BF02574372"],"URL":"https:\/\/doi.org\/10.1007\/bf02574372","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,7]]},"assertion":[{"value":"9 March 1993","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 1994","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}