Stratified Random Sampling over Streaming and Stored Data Article Swipe
Trong Duc Nguyen
,
Ming‐Hung Shih
,
Divesh Srivastava
,
Srikanta Tirthapura
,
Bojian Xu
·
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.5441/002/edbt.2019.04
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.5441/002/edbt.2019.04
Stratified random sampling (SRS) is a widely used sampling technique for approximate query processing. We consider SRS on continuously arriving data streams and statically stored data sets. We present a tight lower bound showing that any streaming algorithm for SRS over the entire stream must have, in the worst case, a variance that is $$\varOmega (r)$$ factor away from the optimal, where r is the number of strata. We present S-VOILA, a practical streaming algorithm for SRS over the entire stream that is locally variance-optimal. We prove that any sliding window-based streaming SRS needs a workspace of $$\varOmega (rM\log W)$$ in the worst case, to maintain a variance-optimal SRS of size M, where W is the number of elements in the sliding window. Due to the inherent high workspace needs for sliding window-based SRS, we present SW-VOILA, a multi-layer practical sampling algorithm that uses only O(M) workspace but can maintain an SRS of size close to M in practice over a sliding window. Experiments show that both S-VOILA and SW-VOILA result in a variance that is typically close to their optimal offline counterparts, which was given the entire input beforehand. We also present VOILA, a variance-optimal offline algorithm for stratified random sampling. VOILA is a strict generalization of the well-known Neyman allocation, which is optimal only under the assumption that each stratum is abundant. Experiments show that VOILA can have significantly smaller variance (1.4x to 50x) than Neyman allocation on real-world data.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.5441/002/edbt.2019.04
- OA Status
- green
- Cited By
- 20
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2932740801
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2932740801Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.5441/002/edbt.2019.04Digital Object Identifier
- Title
-
Stratified Random Sampling over Streaming and Stored DataWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2019Year of publication
- Publication date
-
2019-01-01Full publication date if available
- Authors
-
Trong Duc Nguyen, Ming‐Hung Shih, Divesh Srivastava, Srikanta Tirthapura, Bojian XuList of authors in order
- Landing page
-
https://doi.org/10.5441/002/edbt.2019.04Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://doi.org/10.5441/002/edbt.2019.04Direct OA link when available
- Concepts
-
Mathematics, Sliding window protocol, Upper and lower bounds, Sampling (signal processing), Variance (accounting), Generalization, Streaming algorithm, Algorithm, Computer science, Window (computing), Filter (signal processing), Mathematical analysis, Computer vision, Accounting, Business, Operating systemTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
20Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 6, 2023: 6, 2021: 1, 2020: 6, 2019: 1Per-year citation counts (last 5 years)
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2932740801 |
|---|---|
| doi | https://doi.org/10.5441/002/edbt.2019.04 |
| ids.doi | https://doi.org/10.5441/002/edbt.2019.04 |
| ids.mag | 2932740801 |
| ids.openalex | https://openalex.org/W2932740801 |
| fwci | |
| type | article |
| title | Stratified Random Sampling over Streaming and Stored Data |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12761 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9987000226974487 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Data Stream Mining Techniques |
| topics[1].id | https://openalex.org/T11106 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.989799976348877 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1711 |
| topics[1].subfield.display_name | Signal Processing |
| topics[1].display_name | Data Management and Algorithms |
| topics[2].id | https://openalex.org/T10317 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9872999787330627 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Advanced Database Systems and Queries |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C33923547 |
| concepts[0].level | 0 |
| concepts[0].score | 0.6512025594711304 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[0].display_name | Mathematics |
| concepts[1].id | https://openalex.org/C102392041 |
| concepts[1].level | 3 |
| concepts[1].score | 0.6005405187606812 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q592860 |
| concepts[1].display_name | Sliding window protocol |
| concepts[2].id | https://openalex.org/C77553402 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5562421083450317 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[2].display_name | Upper and lower bounds |
| concepts[3].id | https://openalex.org/C140779682 |
| concepts[3].level | 3 |
| concepts[3].score | 0.5243846774101257 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q210868 |
| concepts[3].display_name | Sampling (signal processing) |
| concepts[4].id | https://openalex.org/C196083921 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5119487047195435 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q7915758 |
| concepts[4].display_name | Variance (accounting) |
| concepts[5].id | https://openalex.org/C177148314 |
| concepts[5].level | 2 |
| concepts[5].score | 0.45588386058807373 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q170084 |
| concepts[5].display_name | Generalization |
| concepts[6].id | https://openalex.org/C187166803 |
| concepts[6].level | 3 |
| concepts[6].score | 0.4504028260707855 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2835831 |
| concepts[6].display_name | Streaming algorithm |
| concepts[7].id | https://openalex.org/C11413529 |
| concepts[7].level | 1 |
| concepts[7].score | 0.4374730885028839 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[7].display_name | Algorithm |
| concepts[8].id | https://openalex.org/C41008148 |
| concepts[8].level | 0 |
| concepts[8].score | 0.28843891620635986 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[8].display_name | Computer science |
| concepts[9].id | https://openalex.org/C2778751112 |
| concepts[9].level | 2 |
| concepts[9].score | 0.2826683521270752 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q835016 |
| concepts[9].display_name | Window (computing) |
| concepts[10].id | https://openalex.org/C106131492 |
| concepts[10].level | 2 |
| concepts[10].score | 0.12581288814544678 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q3072260 |
| concepts[10].display_name | Filter (signal processing) |
| concepts[11].id | https://openalex.org/C134306372 |
| concepts[11].level | 1 |
| concepts[11].score | 0.07719215750694275 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[11].display_name | Mathematical analysis |
| concepts[12].id | https://openalex.org/C31972630 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q844240 |
| concepts[12].display_name | Computer vision |
| concepts[13].id | https://openalex.org/C121955636 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q4116214 |
| concepts[13].display_name | Accounting |
| concepts[14].id | https://openalex.org/C144133560 |
| concepts[14].level | 0 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q4830453 |
| concepts[14].display_name | Business |
| concepts[15].id | https://openalex.org/C111919701 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q9135 |
| concepts[15].display_name | Operating system |
| keywords[0].id | https://openalex.org/keywords/mathematics |
| keywords[0].score | 0.6512025594711304 |
| keywords[0].display_name | Mathematics |
| keywords[1].id | https://openalex.org/keywords/sliding-window-protocol |
| keywords[1].score | 0.6005405187606812 |
| keywords[1].display_name | Sliding window protocol |
| keywords[2].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[2].score | 0.5562421083450317 |
| keywords[2].display_name | Upper and lower bounds |
| keywords[3].id | https://openalex.org/keywords/sampling |
| keywords[3].score | 0.5243846774101257 |
| keywords[3].display_name | Sampling (signal processing) |
| keywords[4].id | https://openalex.org/keywords/variance |
| keywords[4].score | 0.5119487047195435 |
| keywords[4].display_name | Variance (accounting) |
| keywords[5].id | https://openalex.org/keywords/generalization |
| keywords[5].score | 0.45588386058807373 |
| keywords[5].display_name | Generalization |
| keywords[6].id | https://openalex.org/keywords/streaming-algorithm |
| keywords[6].score | 0.4504028260707855 |
| keywords[6].display_name | Streaming algorithm |
| keywords[7].id | https://openalex.org/keywords/algorithm |
| keywords[7].score | 0.4374730885028839 |
| keywords[7].display_name | Algorithm |
| keywords[8].id | https://openalex.org/keywords/computer-science |
| keywords[8].score | 0.28843891620635986 |
| keywords[8].display_name | Computer science |
| keywords[9].id | https://openalex.org/keywords/window |
| keywords[9].score | 0.2826683521270752 |
| keywords[9].display_name | Window (computing) |
| keywords[10].id | https://openalex.org/keywords/filter |
| keywords[10].score | 0.12581288814544678 |
| keywords[10].display_name | Filter (signal processing) |
| keywords[11].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[11].score | 0.07719215750694275 |
| keywords[11].display_name | Mathematical analysis |
| language | en |
| locations[0].id | doi:10.5441/002/edbt.2019.04 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S7407053003 |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Movebank |
| locations[0].source.host_organization | |
| locations[0].source.host_organization_name | |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | |
| locations[0].raw_type | dataset |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://doi.org/10.5441/002/edbt.2019.04 |
| indexed_in | datacite |
| authorships[0].author.id | https://openalex.org/A5010500748 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-6072-628X |
| authorships[0].author.display_name | Trong Duc Nguyen |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I173911158 |
| authorships[0].affiliations[0].raw_affiliation_string | Iowa State University, Ames, United States |
| authorships[0].institutions[0].id | https://openalex.org/I173911158 |
| authorships[0].institutions[0].ror | https://ror.org/04rswrd78 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I173911158 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | Iowa State University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Trong Duc Nguyen |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Iowa State University, Ames, United States |
| authorships[1].author.id | https://openalex.org/A5102827423 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Ming‐Hung Shih |
| authorships[1].countries | US |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I173911158 |
| authorships[1].affiliations[0].raw_affiliation_string | Iowa State University, Ames, United States |
| authorships[1].institutions[0].id | https://openalex.org/I173911158 |
| authorships[1].institutions[0].ror | https://ror.org/04rswrd78 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I173911158 |
| authorships[1].institutions[0].country_code | US |
| authorships[1].institutions[0].display_name | Iowa State University |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ming-Hung Shih |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Iowa State University, Ames, United States |
| authorships[2].author.id | https://openalex.org/A5088315797 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-7609-9217 |
| authorships[2].author.display_name | Divesh Srivastava |
| authorships[2].countries | US |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I1283103587 |
| authorships[2].affiliations[0].raw_affiliation_string | AT&T (United States), Bedminster, United States |
| authorships[2].institutions[0].id | https://openalex.org/I1283103587 |
| authorships[2].institutions[0].ror | https://ror.org/02bbd5539 |
| authorships[2].institutions[0].type | company |
| authorships[2].institutions[0].lineage | https://openalex.org/I1283103587 |
| authorships[2].institutions[0].country_code | US |
| authorships[2].institutions[0].display_name | AT&T (United States) |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Divesh Srivastava |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | AT&T (United States), Bedminster, United States |
| authorships[3].author.id | https://openalex.org/A5047034711 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-5321-924X |
| authorships[3].author.display_name | Srikanta Tirthapura |
| authorships[3].countries | US |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I173911158 |
| authorships[3].affiliations[0].raw_affiliation_string | Iowa State University, Ames, United States |
| authorships[3].institutions[0].id | https://openalex.org/I173911158 |
| authorships[3].institutions[0].ror | https://ror.org/04rswrd78 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I173911158 |
| authorships[3].institutions[0].country_code | US |
| authorships[3].institutions[0].display_name | Iowa State University |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Srikanta Tirthapura |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Iowa State University, Ames, United States |
| authorships[4].author.id | https://openalex.org/A5058084642 |
| authorships[4].author.orcid | https://orcid.org/0000-0001-5642-6826 |
| authorships[4].author.display_name | Bojian Xu |
| authorships[4].countries | US |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I159107703 |
| authorships[4].affiliations[0].raw_affiliation_string | Eastern Washington University, Cheney, United States |
| authorships[4].institutions[0].id | https://openalex.org/I159107703 |
| authorships[4].institutions[0].ror | https://ror.org/002g57a93 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I159107703 |
| authorships[4].institutions[0].country_code | US |
| authorships[4].institutions[0].display_name | Eastern Washington University |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Bojian Xu |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | Eastern Washington University, Cheney, United States |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://doi.org/10.5441/002/edbt.2019.04 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Stratified Random Sampling over Streaming and Stored Data |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12761 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9987000226974487 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Data Stream Mining Techniques |
| related_works | https://openalex.org/W2315793668, https://openalex.org/W3009386101, https://openalex.org/W2152637787, https://openalex.org/W1982766109, https://openalex.org/W2571425027, https://openalex.org/W1768722274, https://openalex.org/W2128175693, https://openalex.org/W2910815838, https://openalex.org/W2080099515, https://openalex.org/W3127802713, https://openalex.org/W2321010360, https://openalex.org/W1998058823, https://openalex.org/W2012365979, https://openalex.org/W1554887429, https://openalex.org/W3172712527, https://openalex.org/W2950346378, https://openalex.org/W2151150590, https://openalex.org/W2133577012, https://openalex.org/W1570512705, https://openalex.org/W91584380 |
| cited_by_count | 20 |
| counts_by_year[0].year | 2024 |
| counts_by_year[0].cited_by_count | 6 |
| counts_by_year[1].year | 2023 |
| counts_by_year[1].cited_by_count | 6 |
| counts_by_year[2].year | 2021 |
| counts_by_year[2].cited_by_count | 1 |
| counts_by_year[3].year | 2020 |
| counts_by_year[3].cited_by_count | 6 |
| counts_by_year[4].year | 2019 |
| counts_by_year[4].cited_by_count | 1 |
| locations_count | 1 |
| best_oa_location.id | doi:10.5441/002/edbt.2019.04 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S7407053003 |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Movebank |
| best_oa_location.source.host_organization | |
| best_oa_location.source.host_organization_name | |
| best_oa_location.license | |
| best_oa_location.pdf_url | |
| best_oa_location.version | |
| best_oa_location.raw_type | dataset |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://doi.org/10.5441/002/edbt.2019.04 |
| primary_location.id | doi:10.5441/002/edbt.2019.04 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S7407053003 |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Movebank |
| primary_location.source.host_organization | |
| primary_location.source.host_organization_name | |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | |
| primary_location.raw_type | dataset |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://doi.org/10.5441/002/edbt.2019.04 |
| publication_date | 2019-01-01 |
| publication_year | 2019 |
| referenced_works_count | 0 |
| abstract_inverted_index.M | 348 |
| abstract_inverted_index.W | 305 |
| abstract_inverted_index.a | 5, 29, 50, 167, 190, 298, 329, 352, 364, 386, 396 |
| abstract_inverted_index.r | 158 |
| abstract_inverted_index.M, | 303 |
| abstract_inverted_index.We | 14, 27, 164, 181, 382 |
| abstract_inverted_index.an | 342 |
| abstract_inverted_index.in | 46, 292, 311, 349, 363 |
| abstract_inverted_index.is | 4, 53, 159, 178, 306, 367, 395, 405, 414 |
| abstract_inverted_index.of | 162, 192, 301, 309, 344, 399 |
| abstract_inverted_index.on | 17, 431 |
| abstract_inverted_index.to | 296, 316, 347, 370, 426 |
| abstract_inverted_index.we | 326 |
| abstract_inverted_index.Due | 315 |
| abstract_inverted_index.SRS | 16, 39, 172, 188, 300, 343 |
| abstract_inverted_index.and | 22, 360 |
| abstract_inverted_index.any | 35, 184 |
| abstract_inverted_index.but | 339 |
| abstract_inverted_index.can | 340, 420 |
| abstract_inverted_index.for | 10, 38, 171, 322, 390 |
| abstract_inverted_index.the | 41, 47, 155, 160, 174, 293, 307, 312, 317, 378, 400, 409 |
| abstract_inverted_index.was | 376 |
| abstract_inverted_index.50x) | 427 |
| abstract_inverted_index.O(M) | 337 |
| abstract_inverted_index.SRS, | 325 |
| abstract_inverted_index.also | 383 |
| abstract_inverted_index.away | 153 |
| abstract_inverted_index.both | 358 |
| abstract_inverted_index.data | 20, 25 |
| abstract_inverted_index.each | 412 |
| abstract_inverted_index.from | 154 |
| abstract_inverted_index.have | 421 |
| abstract_inverted_index.high | 319 |
| abstract_inverted_index.must | 44 |
| abstract_inverted_index.only | 336, 407 |
| abstract_inverted_index.over | 40, 173, 351 |
| abstract_inverted_index.show | 356, 417 |
| abstract_inverted_index.size | 302, 345 |
| abstract_inverted_index.than | 428 |
| abstract_inverted_index.that | 34, 52, 177, 183, 334, 357, 366, 411, 418 |
| abstract_inverted_index.used | 7 |
| abstract_inverted_index.uses | 335 |
| abstract_inverted_index.(1.4x | 425 |
| abstract_inverted_index.(SRS) | 3 |
| abstract_inverted_index.VOILA | 394, 419 |
| abstract_inverted_index.W)$$ | 261 |
| abstract_inverted_index.bound | 32 |
| abstract_inverted_index.case, | 49, 295 |
| abstract_inverted_index.close | 346, 369 |
| abstract_inverted_index.given | 377 |
| abstract_inverted_index.have, | 45 |
| abstract_inverted_index.input | 380 |
| abstract_inverted_index.lower | 31 |
| abstract_inverted_index.needs | 189, 321 |
| abstract_inverted_index.prove | 182 |
| abstract_inverted_index.query | 12 |
| abstract_inverted_index.sets. | 26 |
| abstract_inverted_index.their | 371 |
| abstract_inverted_index.tight | 30 |
| abstract_inverted_index.under | 408 |
| abstract_inverted_index.where | 157, 304 |
| abstract_inverted_index.which | 375, 404 |
| abstract_inverted_index.worst | 48, 294 |
| abstract_inverted_index.(r)$$ | 121 |
| abstract_inverted_index.Neyman | 402, 429 |
| abstract_inverted_index.VOILA, | 385 |
| abstract_inverted_index.entire | 42, 175, 379 |
| abstract_inverted_index.factor | 152 |
| abstract_inverted_index.number | 161, 308 |
| abstract_inverted_index.random | 1, 392 |
| abstract_inverted_index.result | 362 |
| abstract_inverted_index.stored | 24 |
| abstract_inverted_index.stream | 43, 176 |
| abstract_inverted_index.strict | 397 |
| abstract_inverted_index.widely | 6 |
| abstract_inverted_index.(rM\log | 260 |
| abstract_inverted_index.S-VOILA | 359 |
| abstract_inverted_index.locally | 179 |
| abstract_inverted_index.offline | 373, 388 |
| abstract_inverted_index.optimal | 372, 406 |
| abstract_inverted_index.present | 28, 165, 327, 384 |
| abstract_inverted_index.showing | 33 |
| abstract_inverted_index.sliding | 185, 313, 323, 353 |
| abstract_inverted_index.smaller | 423 |
| abstract_inverted_index.strata. | 163 |
| abstract_inverted_index.stratum | 413 |
| abstract_inverted_index.streams | 21 |
| abstract_inverted_index.window. | 314, 354 |
| abstract_inverted_index.S-VOILA, | 166 |
| abstract_inverted_index.SW-VOILA | 361 |
| abstract_inverted_index.arriving | 19 |
| abstract_inverted_index.consider | 15 |
| abstract_inverted_index.elements | 310 |
| abstract_inverted_index.inherent | 318 |
| abstract_inverted_index.maintain | 297, 341 |
| abstract_inverted_index.optimal, | 156 |
| abstract_inverted_index.practice | 350 |
| abstract_inverted_index.sampling | 2, 8, 332 |
| abstract_inverted_index.variance | 51, 365, 424 |
| abstract_inverted_index.SW-VOILA, | 328 |
| abstract_inverted_index.abundant. | 415 |
| abstract_inverted_index.algorithm | 37, 170, 333, 389 |
| abstract_inverted_index.practical | 168, 331 |
| abstract_inverted_index.sampling. | 393 |
| abstract_inverted_index.streaming | 36, 169, 187 |
| abstract_inverted_index.technique | 9 |
| abstract_inverted_index.typically | 368 |
| abstract_inverted_index.workspace | 191, 320, 338 |
| abstract_inverted_index.Stratified | 0 |
| abstract_inverted_index.allocation | 430 |
| abstract_inverted_index.assumption | 410 |
| abstract_inverted_index.statically | 23 |
| abstract_inverted_index.stratified | 391 |
| abstract_inverted_index.well-known | 401 |
| abstract_inverted_index.$$\varOmega | 120, 259 |
| abstract_inverted_index.Experiments | 355, 416 |
| abstract_inverted_index.allocation, | 403 |
| abstract_inverted_index.approximate | 11 |
| abstract_inverted_index.beforehand. | 381 |
| abstract_inverted_index.multi-layer | 330 |
| abstract_inverted_index.processing. | 13 |
| abstract_inverted_index.continuously | 18 |
| abstract_inverted_index.window-based | 186, 324 |
| abstract_inverted_index.counterparts, | 374 |
| abstract_inverted_index.significantly | 422 |
| abstract_inverted_index.generalization | 398 |
| abstract_inverted_index.variance-optimal | 299, 387 |
| abstract_inverted_index.real-world data. | 432 |
| abstract_inverted_index.variance-optimal. | 180 |
| cited_by_percentile_year | |
| countries_distinct_count | 1 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile |