NDLI: Lower bounds for sorting with few random accesses to external memory

Please wait, while we are loading the content...

Context-sensitive program analysis as database queries

XML data exchange: consistency and query answering

Schema mappings, data exchange, and metadata management

On the complexity of division and set joins in the relational algebra

Security analysis of cryptographically controlled access to XML documents

Computing cores for data exchange: new algorithms and practical solutions

Multi-structural databases

Buffering in query evaluation over XML streams

Operator placement for in-network stream query processing

XML type checking with macro tree transducers

Models and methods for privacy-preserving data publishing and analysis: invited tutorial

Estimating arbitrary subset sums with few probes

Differential constraints

XPath satisfiability in the presence of DTDs

On the complexity of nonrecursive XQuery and functional query languages on complex values

Simulatable auditing

Peer data exchange

A divide-and-merge methodology for clustering

Histograms revisited: when are histograms the best approximation method for aggregates over joins?

Join-distinct aggregate estimation over update streams

Regular rewriting of active XML and unambiguity

Diagnosis of asynchronous discrete event systems: datalog to the rescue!

Deciding well-definedness of XQuery fragments

An incremental algorithm for computing ranked full disjunctions

Practical privacy: the SuLQ framework

Composition of mappings given by embedded dependencies

Allocating isolation levels to transactions

Lower bounds for sorting with few random accesses to external memory

Space efficient mining of multigraph streams

Determining source contribution in integration systems

Space complexity of hierarchical heavy hitters in multi-dimensional data streams

Relative risk and odds ratio: a data mining perspective

Views and queries: determinacy and rewriting

Privacy-enhancing k-anonymization of customer data

Lower bounds for sorting with few random accesses to external memory

Content Provider	ACM Digital Library
Author	Schweikardt, Nicole Grohe, Martin
Abstract	We consider a scenario where we want to query a large dataset that is stored in external memory and does not fit into main memory. The most constrained resources in such a situation are the size of the main memory and the number of random accesses to external memory. We note that sequentially streaming data from external memory through main memory is much less prohibitive.We propose an abstract model of this scenario in which we restrict the size of the main memory and the number of random accesses to external memory, but do not restrict sequential reads. A distinguishing feature of our model is that it admits the usage of unlimited external memory for storing intermediate results, such as several hard disks that can be accessed in parallel. In practice, such auxiliary external memory can be crucial. For example, in a first sequential pass the data can be annotated, and in a second pass this annotation can be used to answer the query. Koch's [9] ARB system for answering XPath queries is based on such a strategy.In this model, we prove lower bounds for sorting the input data. As opposed to related results for models without auxiliary external memory for intermediate results, we cannot rely on communication complexity to establish these lower bounds. Instead, we simulate. our model by a non-uniform computation model for which we can establish the lower bounds by combinatorial means.
Starting Page	238
Ending Page	249
Page Count	12
File Format	PDF
ISBN	1595930620
DOI	10.1145/1065167.1065197
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-06-13
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Lower Bounds for Processing Data with Few Random Accesses to External Memory

Lower bounds for processing data with few random accesses to external memory.

Lower bounds for processing data with few random accesses to external memory (2009).

Lower bounds for sorting with few random accesses to external memory (2005)

Lower bounds for processing data with few random accesses to external memory

Lower Bounds in the Asymmetric External Memory Model

Lower bounds for external memory dictionaries

Lower Bounds for Sorting with Realistic Instruction Sets

Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Lower bounds for sorting with few random accesses to external memory

Similar Documents

Lower Bounds for Processing Data with Few Random Accesses to External Memory

Lower bounds for processing data with few random accesses to external memory.

Lower bounds for processing data with few random accesses to external memory (2009).

Lower bounds for sorting with few random accesses to external memory (2005)

Lower bounds for processing data with few random accesses to external memory

Lower Bounds in the Asymmetric External Memory Model

Lower bounds for external memory dictionaries

Lower Bounds for Sorting with Realistic Instruction Sets

Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Lower bounds for sorting with few random accesses to external memory