-1

I need to think of a way to model how one thing is more "changy" than another.

Say I need to index a news website's different news sections with some web crawler. I want to prioritise indexing those sections (e.g. live news or sports) that receive more news items than those that don't (e.g. health or culture).

A crude way that I thought up is to initially have equal probability to pick each news section. I then index them one page at a time (I have this restriction) and each time I index a section, I sum how many news items have been removed, added or updated in that section compared to last time (think of it as a delta) and I use that to adjust the probability of that section being picked for indexing next (e.g. by some weight).

Over time, the live news section will have a bigger weight than something like health or culture, since it will have had more news items added to it or updated (I'm using weighted random choice to randomly select items to pick with some weight consideration) and so will be indexed more frequently to keep up with any new changes.

But I'm not sure how to think of this numerically. What initial weights, factors and ranges make sense? Can I prevent more dynamic sections from completely dominating less dynamic ones for which section gets picked next for indexing (I can only visit one page at a time)? Are there established algorithms that deal with these kinds of problems? Ideally I'll have something that gives a sufficient priority to "changier" sections whilst still allowing less dynamic sections to get indexed.

Improve this question
5
  • 3
    Change can be modeled as a binary state (it's changed or it hasn't). Under that model "changy" can simply be measured as the frequency of that state change. Average duration between changes might be a more human friendly metric. Measures the same thing.
    – candied_orange
    Dec 9, 2021 at 21:49
  • 1
    @candied_orange: "the frequency of that state change" I think OP's core question here is that when he starts listening to those weights, he disproportionately starts checking one source more than the other (based on their weights, as intended); which in turn muddies the frequency measurement, because one of them may have a misrepresented frequency (e.g. the one you check more often has a misleading lower frequency because you check it way too often, or the one you check least often now has a high frequency because you only check it after a long time).
    – Flater
    Dec 10, 2021 at 9:19
  • @Flater that's it, simply adding up the new/changed items in a page every time I crawl it seems naive to me, I thought of maybe having an "age" factor that counterbalances infrequently indexed pages, e.g. if i've not crawled a page in a while do prioritise it
    – anon
    Dec 10, 2021 at 10:57
  • Why the downvote?
    – anon
    Dec 10, 2021 at 11:21
  • 1
    Yeah. Why was this closed. It seems to be generating some interesting answers. Can someone provide some feedback so the question can be improved?
    – Blake
    Dec 10, 2021 at 14:33

2 Answers 2

Reset to default
2

The best alternative would probably be to find some way to extract the update dates of the articles. That would let recreate an accurate timeline of all the changes, and that should let you estimate the average change frequency, and might allow you to do so more fancy things like pattern recognition to spot patterns in posting, like updates only occurring during working hours.

If you cannot get exact times you should still be able to provide an estimated timeline by counting the number of changes made since the last update, and assuming they are distributed evenly during the update interval. Keep a history of the changes some time back and uses this to estimate average change frequency. However, any kind of pattern recognition would probably be less reliable since you lack accurate dates.

Once you have an average change frequency you can simply query the page after some multiple of the change frequency. Since different pages can have different change frequencies they would be sampled at different rates.

You probably want to assume some arbitrary initial change frequency. It is probably also a good idea to limit on how far you look in the timeline, so that changed in change frequency can be picked up on. There are also control engineering techniques, like a PID regulator, that could be applied to provide a faster response to changes.

This would assume that a "change" is a distinct event, but it might be possible to weight changes according to if it is a new post, or a edit, the number of words added or changed etc.

Improve this answer
2
  • Thank you for the answer, assuming I can't use dates, does this account for the potential to over/under sample specific pages? Also, can you recommend some other techniques or algorithms from operations/control research? I'll definitely look into PID controllers.
    – anon
    Dec 10, 2021 at 11:31
  • 1
    @Nobilis As long as you can keep history to get a reasonably accurate change frequency, you should be able to adjust the sample rate to match. And it should be possible to estimate said frequency regardless of your chosen sample rate, even if said sample rate changes. I'm not really an expert on control research, so I would just suggest to keep it simple.
    – JonasH
    Dec 10, 2021 at 12:24
0

RSS is still a thing.

While not obvious, a lot of news websites still support RSS and, if recent news are anything to go by with, this old-but-lovely protocol seems to be making a comeback nowadays.

Go hit up the RSS feeds of the news website you want to crawl. The feeds will have the links for the latest articles and relevant updates, so you'll know exactly "What's new" and what do you have to crawl.

Improve this answer
2
  • RSS is a fair suggestion or even APIs where available but I am after a general way to model changiness since I need to index sites that might not expose an API or an RSS feed (and I'm also interested in this as a problem to solve, I know little about operations research/control theory and thought it might be possible to use a technique from these fields to model my problem).
    – anon
    Dec 10, 2021 at 11:38
  • Then I'm afraid I won't be able to help you. Either your crawler is context-sensitive, and thus is tailored to a specific site with a specific layout, or it is general - and thus can't prioritize things and just walks around everything collecting data. Creating a crawler that is both context-sensitive while still being very general is not impossible, but kinda hard of a problem to tackle on a Stack Question. At this point you're slowly walking towards Machine Learning, and that's somewhat of a complex topic.
    – T. Sar
    Dec 10, 2021 at 13:02