User loginNavigation |
Graph processingHi all, Not sure if this is a good forum to post this question on, but it's the best I could come up with, so hopefully someone will have some insights or pointers as to where to look for research :) I've been thinking about 'graph processing' systems (for want of a better name) - for example, say an image editing system where an output image is described by a process on various input images, and those input images are again described by more processes on further inputs, and so on. A DAG basically, where each node is a process that produces an item of data, and the edges represent dependencies on input data. Now say I wrote an image editing application based on such a system. I'd like to allow users to edit any process, thereby meaning all downstream nodes need recalculating, but to achieve best performance, ideally upstream nodes of the thing being edited would be cached somewhere - so you don't need to continually re-evalute any inputs whilst editing. However, clearly you've only got a limited amount of memory to cache stuff in, and therefore can't cache everything, so how do you decide which nodes should be cached and which shouldn't? Kind of feels like if you could assign each process a cost (i.e. how expensive it is to recalculate the output of a node from its inputs), and a probability that it will be edited (i.e. there's no point in caching something if nothing downstream of it changes, but if a process is continually edited you'll probably want to cache it's inputs), then there ought to be some way of determining roughly which processes should be cached and which shouldn't. Seems like it ought to be possible to do better than just a simple LRU cache of node outputs for example. Feels like it's probably a problem that's been researched somewhere in some form or other, or it's some computer science 101 problem I happened to miss out on phrased in somewhat odd terms, but I'm at a loss as to where to start looking... Any pointers appreciated...! By richk at 2010-01-24 21:37 | LtU Forum | previous forum topic | next forum topic | other blogs | 5671 reads
|
Browse archives
Active forum topics |
Recent comments
17 weeks 8 hours ago
17 weeks 12 hours ago
17 weeks 12 hours ago
39 weeks 1 day ago
43 weeks 3 days ago
45 weeks 20 hours ago
45 weeks 20 hours ago
47 weeks 5 days ago
1 year 2 days ago
1 year 2 days ago