* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Sunday, June 8, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Ceramic Dalmatian Entertainment is WLAF’s Business of the Week – WLAF

    Spotlight on Success: Ceramic Dalmatian Entertainment Shines as This Week’s Featured Business!

    Brass Lion Entertainment unveils co-op action RPG Wu-Tang: Rise of the Deceiver – VentureBeat

    Unleash Your Inner Warrior: Discover the Co-Op Action RPG Wu-Tang: Rise of the Deceiver!

    Entertainment lineup released for 2025 Mississippi State Fair – WAPT

    Exciting Entertainment Lineup Unveiled for the 2025 Mississippi State Fair!

    After Denzel Washington Said He Would Be In Black Panther 3, Ryan Coogler Explained Why He’s ‘Fine’ With That Information Being Revealed So Early – Yahoo

    Ryan Coogler Shares Why He’s Cool with Denzel Washington’s Black Panther 3 Reveal!

    Traveling Tacos and Tequila Festival to stop at Florence Yall’s stadium this October – Cincinnati Enquirer

    Get Ready for a Flavor Fiesta: Traveling Tacos and Tequila Festival Hits Florence Y’all’s Stadium This October!

    9 things to do this weekend in Lake County plus a look ahead – Leesburg Daily Commercial

    Discover 9 Exciting Weekend Adventures in Lake County and What’s Coming Up!

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    Drag racer survives frightening airborne crash at World Wide Technology Raceway – FOX 2

    Drag racer survives frightening airborne crash at World Wide Technology Raceway – FOX 2

    Apple Watch and the future of wearable technology in healthcare – MSN

    Revolutionizing Healthcare: The Future of Wearable Technology with Apple Watch

    ECS Professor Pankaj K. Jha Receives NSF Grant to Develop Quantum Technology – Syracuse University News

    Unlocking the Future: ECS Professor Pankaj K. Jha Secures NSF Grant for Groundbreaking Quantum Technology Development

    Fire Tech Brief: 5 Fire Apparatus Technology Upgrades – firehouse.com

    Revving Up Safety: 5 Innovative Upgrades for Fire Apparatus Technology

    U.S. FDA Grants Platform Technology Designation to the Viral Vector Used in SRP-9003, Sarepta’s Investigational Gene Therapy for the Treatment of Limb Girdle Muscular Dystrophy Type 2E/R4 – Sarepta Therapeutics

    Breakthrough for Gene Therapy: FDA Designates Viral Vector in Sarepta’s SRP-9003 for Limb Girdle Muscular Dystrophy Treatment

    Waunakee Fifth-Graders Dive into the Future at Exciting Tech Day!

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Ceramic Dalmatian Entertainment is WLAF’s Business of the Week – WLAF

    Spotlight on Success: Ceramic Dalmatian Entertainment Shines as This Week’s Featured Business!

    Brass Lion Entertainment unveils co-op action RPG Wu-Tang: Rise of the Deceiver – VentureBeat

    Unleash Your Inner Warrior: Discover the Co-Op Action RPG Wu-Tang: Rise of the Deceiver!

    Entertainment lineup released for 2025 Mississippi State Fair – WAPT

    Exciting Entertainment Lineup Unveiled for the 2025 Mississippi State Fair!

    After Denzel Washington Said He Would Be In Black Panther 3, Ryan Coogler Explained Why He’s ‘Fine’ With That Information Being Revealed So Early – Yahoo

    Ryan Coogler Shares Why He’s Cool with Denzel Washington’s Black Panther 3 Reveal!

    Traveling Tacos and Tequila Festival to stop at Florence Yall’s stadium this October – Cincinnati Enquirer

    Get Ready for a Flavor Fiesta: Traveling Tacos and Tequila Festival Hits Florence Y’all’s Stadium This October!

    9 things to do this weekend in Lake County plus a look ahead – Leesburg Daily Commercial

    Discover 9 Exciting Weekend Adventures in Lake County and What’s Coming Up!

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    Drag racer survives frightening airborne crash at World Wide Technology Raceway – FOX 2

    Drag racer survives frightening airborne crash at World Wide Technology Raceway – FOX 2

    Apple Watch and the future of wearable technology in healthcare – MSN

    Revolutionizing Healthcare: The Future of Wearable Technology with Apple Watch

    ECS Professor Pankaj K. Jha Receives NSF Grant to Develop Quantum Technology – Syracuse University News

    Unlocking the Future: ECS Professor Pankaj K. Jha Secures NSF Grant for Groundbreaking Quantum Technology Development

    Fire Tech Brief: 5 Fire Apparatus Technology Upgrades – firehouse.com

    Revving Up Safety: 5 Innovative Upgrades for Fire Apparatus Technology

    U.S. FDA Grants Platform Technology Designation to the Viral Vector Used in SRP-9003, Sarepta’s Investigational Gene Therapy for the Treatment of Limb Girdle Muscular Dystrophy Type 2E/R4 – Sarepta Therapeutics

    Breakthrough for Gene Therapy: FDA Designates Viral Vector in Sarepta’s SRP-9003 for Limb Girdle Muscular Dystrophy Treatment

    Waunakee Fifth-Graders Dive into the Future at Exciting Tech Day!

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
Earth-News
No Result
View All Result
Home Science

Computer Scientists Invent an Efficient New Way to Count

May 17, 2024
in Science
Computer Scientists Invent an Efficient New Way to Count
Share on FacebookShare on Twitter

Nico Roper/Quanta Magazine

Introduction

Imagine that you’re sent to a pristine rainforest to carry out a wildlife census. Every time you see an animal, you snap a photo. Your digital camera will track the total number of shots, but you’re only interested in the number of unique animals — all the ones that you haven’t counted already. What’s the best way to get that number? “The obvious solution requires remembering every animal you’ve seen so far and comparing each new animal to the list,” said Lance Fortnow, a computer scientist at the Illinois Institute of Technology. But there are cleverer ways to proceed, he added, because if you have thousands of entries, the obvious approach is far from easy.

It gets worse. What if you’re Facebook, and you want to count the number of distinct users who log in each day, even if some of them log in from multiple devices and at multiple times? Now we’re comparing each new login to a list that could run to the billions.

In a recent paper, computer scientists have described a new way to approximate the number of distinct entries in a long list, a method that requires remembering only a small number of entries. The algorithm will work for any list where the items come in one at a time — think words in a speech, goods on a conveyor belt or cars on the interstate.

The CVM algorithm, named for its creators — Sourav Chakraborty of the Indian Statistical Institute, Vinodchandran Variyam of the University of Nebraska, Lincoln, and Kuldeep Meel of the University of Toronto — is a significant step toward solving what’s called the distinct elements problem, which computer scientists have grappled with for more than 40 years. It asks for a way to efficiently monitor a stream of elements — the total number of which may exceed available memory — and then estimate the number of unique elements.

“The new algorithm is astonishingly simple and easy to implement,” said Andrew McGregor of the University of Massachusetts, Amherst. “I wouldn’t be surprised if this became the default way the [distinct elements] problem is approached in practice.”

To illustrate both the problem and how the CVM algorithm solves it, imagine that you’re listening to the audiobook of Hamlet. There are 30,557 words in the play. How many are distinct? To find out, you could listen to the play (making frequent use of the pause button), write down each word alphabetically in a notebook, and skip over words already on your list. When you reach the end, you’ll just count the number of words on the list. This approach works, but it requires an amount of memory roughly equal to the number of unique words.

In typical data-streaming situations, there could be millions of items to keep track of. “You might not want to store everything,” Variyam said. And that’s where the CVM algorithm can offer an easier way. The trick, he said, is to rely on randomization.

Vinodchandran Variyam in a white shirt and gray jacket sits in front of a bookshelf.

Vinodchandran Variyam helped invent a technique to estimate the number of distinct elements in a stream of data.

Craig Chandler

Introduction

Let’s return to Hamlet, but this time your working memory — consisting of a whiteboard — has room for just 100 words. Once the play starts, you write down the first 100 words you hear, again skipping any repeats. When the space is full, press pause and flip a coin for each word. Heads, and the word stays on the list; tails, and you delete it. After this preliminary round, you’ll have about 50 distinct words left.

Now you move forward with what the team calls Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list. Proceed in this fashion until you have 100 words on the whiteboard. Then randomly delete about half again, based on the outcome of 100 coin tosses. That concludes Round 1.

Next, move to Round 2. Continue as in Round 1, only now we’ll make it harder to keep a word. When you come to a repeated word, flip the coin again. Tails, and you delete it, as before. But if it comes up heads, you’ll flip the coin a second time. Only keep the word if you get a second heads. Once you fill up the board, the round ends with another purge of about half the words, based on 100 coin tosses.

In the third round, you’ll need three heads in a row to keep a word. In the fourth round you’ll need four heads in a row. And so on.

Eventually, in the kth round, you’ll reach the end of Hamlet. The point of the exercise has been to ensure that every word, by virtue of the random selections you’ve made, has the same probability of being there: 1/2k. If, for instance, you have 61 words on your list at the conclusion of Hamlet, and the process took six rounds, you can divide 61 by the probability, 1/26, to estimate the number of distinct words — which comes out to 3,904 in this case. (It’s easy to see how this procedure works: Suppose you start with 100 coins and flip each one individually, keeping only those that come up heads. You’ll end up with close to 50 coins, and if someone divides that number by the probability, ½, they can guess that there were about 100 coins originally.)

Variyam and his colleagues mathematically proved that the accuracy of this technique scales with the size of the memory. Hamlet has exactly 3,967 unique words. (They counted.) In experiments using a memory of 100 words, the average estimate after five runs was 3,955 words. With a memory of 1,000 words, the average improved to 3,964. “Of course,” he said, “if the [memory] is so big that it fits all the words, then we can get 100% accuracy.”

“This is a great example of how, even for very basic and well-studied problems, there are sometimes very simple but non-obvious solutions still waiting to be discovered,” said William Kuszmaul of Harvard University.

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/

Tags: ComputerscienceScientists
Previous Post

Dichlorprop, Proposed Maximum Residue Limit (PMRL2024-07)

Next Post

Epiregulin: The Growth Factor Redefining Human Brain Evolution

designing for ‘abundance,’ with ecological landscaper kelly norris – A Way To Garden

Embracing Abundance: Insights from Ecological Landscaper Kelly Norris

June 8, 2025
How to take photos on your phone via remote control – Popular Science

How to take photos on your phone via remote control – Popular Science

June 8, 2025
Opinion | RFK Jr.’s Deadly War on Science – Common Dreams

RFK Jr.’s Dangerous Assault on Science: A Call to Action

June 8, 2025
The Worst Bonne Maman Preserves Flavor Leaves A Lot To Be Desired – Yahoo

The Worst Bonne Maman Preserves Flavor Leaves A Lot To Be Desired – Yahoo

June 8, 2025
D.C. Hosts WorldPride Parade in the Shadow of Trump – The New York Times

Celebrating Love and Unity: D.C. Lights Up for WorldPride Parade Amidst Political Tensions

June 8, 2025
This New England state has the best economy in the country, according to WalletHub – Boston.com

Discover the New England State Boasting the Strongest Economy in the Nation!

June 8, 2025
Ceramic Dalmatian Entertainment is WLAF’s Business of the Week – WLAF

Spotlight on Success: Ceramic Dalmatian Entertainment Shines as This Week’s Featured Business!

June 8, 2025
Billy Joel jokes about aging, cremation after brain disorder diagnosis – Fox News

Billy Joel Shares Hilarious Takes on Aging and Life After a Health Scare

June 8, 2025
Supreme Court restores DOGE’s access to sensitive Social Security data and says it doesn’t have to turn over documents – CNN

Supreme Court Grants DOGE Access to Sensitive Social Security Data, Protects Confidential Documents!

June 8, 2025
Drag racer survives frightening airborne crash at World Wide Technology Raceway – FOX 2

Drag racer survives frightening airborne crash at World Wide Technology Raceway – FOX 2

June 8, 2025

Categories

Archives

June 2025
MTWTFSS
 1
2345678
9101112131415
16171819202122
23242526272829
30 
« May    
Earth-News.info

The Earth News is an independent English-language daily published Website from all around the World News

Browse by Category

  • Business (20,132)
  • Ecology (676)
  • Economy (689)
  • Entertainment (21,595)
  • General (15,271)
  • Health (9,731)
  • Lifestyle (693)
  • News (22,149)
  • People (690)
  • Politics (697)
  • Science (15,908)
  • Sports (21,192)
  • Technology (15,675)
  • World (674)

Recent News

designing for ‘abundance,’ with ecological landscaper kelly norris – A Way To Garden

Embracing Abundance: Insights from Ecological Landscaper Kelly Norris

June 8, 2025
How to take photos on your phone via remote control – Popular Science

How to take photos on your phone via remote control – Popular Science

June 8, 2025
  • About
  • Advertise
  • Privacy & Policy
  • Contact

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

Go to mobile version