Slashdot Mirror
Text-Mining Your E-mail
Misha writes "There have been a number of weeks/months in anyone's life that called for a better organization of your Inbox. filtering and folders work, but it'd be nice to have an text-mining tool running in the background that categorized incoming messages by topic as they arrive. It's nice to see that besides NLP research, there are some great algorithmic advances being done, as seen in this paper. Perhaps even one of them Perl monkeys will quickly hack such a background tool." Note: it's a PostScript file.
They'll end up finding a loophole in your filtering, or you'll end up filtering out real emails.
Only way to win is to kill it from the source. End of story.
Here's to the researchers. I would like:
* An email box that lets me extract the threads with my friends.
* An email box that automatically ages the files effectively archiving them. Some of my mail folders/files are huge now and it takes too long to append them when new mail arrives.
Yes, I realize I should get off my butt and do this, but it's faster to post on slashdot.
Here's a link to a terribly useful site for converting your postscripts and word docs into pdf or jpeg.
I was thinking of how to intentionally fail my drug test... It would make a good memoir story someday.
just get ghostview i mean, u have to get acrobat to read pdf, right? unless you're on OS X or something... get ghostview, clicking on the ps document in mozilla magically invokes it, thus u prevail
I'm sure I'm not alone in saying that having a good history of well filtered incoming, and especially just about all of my Outgoing (Outbox) available for searching. My Outbox has been a lifesaver several times when someone claims that they didn't have that (electronic) discussion with me. It's great to quote "in a message sent... ...I asked you to...".
That feature in the description is not text mining, just filtering.
-pyrrho
It automagically does full text indexing of all specified databases. To it, your Inbox is just another database.
"History doesn't repeat itself, but it does rhyme." Mark Twain
Yeah, a link to an standard document format that you can get viewers for on almost every platform. Damn that's soo inconsiderate, where's those word documents?
This would be an awesome tool to block spam. If this program could look at the text of an email message and determine that it is a solicitation of some kind and then drop it into an email "pit" (you know, a folder mapped to /dev/null), that would make my life a LOT easier...
The Dopester
"Yes, I'm a Karma Whore, but I'm doing it to pay my way through school."
Outlook?
"that categorized incoming messages by topic as they arrive." - you can already sort messages into different folders depending on their topic by setting up rules.
Video Game cheats, hints a
Personally, I'd prefer that I simply get less email. The fact that we need NLP tools to pre-screen our email for us just shows how information-overloaded our society has become. What I really need is a tool at the sender's end that can pre-screen my email and tell the sender "Don't send this. He just doesn't care!"
I can sort reports from devices, co-workers, clients....each goes in its own folder....
Bursty and Hierarchical Structure in Streams * Jon Kleinberg # Abstract A fundamental problem in text data mining is to extract meaningful structure from document streams that arrive continuously over time. E-mail and news articles are two natural examples of such streams, each characterized by topics that appear, grow in intensity for a period of time, and then fade away. The published literature in a particular research field can be seen to exhibit similar phenomena over a much longer time scale. Underlying much of the text mining work in this area is the following intuitive premise -- that the appearance of a topic in a document stream is signaled by a "burst of activity," with certain features rising sharply in frequency as the topic emerges. The goal of the present work is to develop a formal approach for modeling such "bursts," in such a way that they can be robustly and efficiently identified, and can provide an organizational framework for analyzing the underlying content. The approach is based on modeling the stream using an infinite-state automaton, in which bursts appear naturally as state transitions; in some ways, it can be viewed as drawing an analogy with models from queueing theory for bursty network traffic. The resulting algorithms are highly efficient, and yield a nested representation of the set of bursts that imposes a hierarchical structure on the overall stream. Experiments with e-mail and research paper archives suggest that the resulting structures have a natural meaning in terms of the content that gave rise to them. *A version of this work appears as Cornell Computer Science Technical Report 02-1863 (March 2002). #Department of Computer Science, Cornell University, Ithaca NY 14853. Email: kleinber@cs.cornell.edu. Supported in part by a David and Lucile Packard Foundation Fellowship, an ONR Young Investigator Award, NSF ITR/IM Grant IIS-0081334, and NSF Faculty Early Career Development Award CCR-9701399. 1. 1 Introduction Documents can be naturally organized by topic, but in many settings we also experience their arrival over time. E-mail and news articles provide two clear examples of such document streams: in both cases, the strong temporal ordering of the content is necessary for making sense of it, as particular topics appear, grow in intensity, and then fade away again. Over a much longer time scale, the published literature in a particular research field can be meaningfully understood in this way as well, with particular research themes growing and diminishing in visibility across a period of years. Work in the areas of topic detection and tracking [2, 3, 5, 61, 62], text mining [36, 56, 57, 58], and visualization [26, 43, 60] has explored techniques for identifying topics in document streams comprised of news stories, using a combination of content analysis and time-series modeling. Underlying a number of these techniques is the following intuitive premise -- that the appearance of a topic in a document stream is signaled by a "burst of activity," with certain features rising sharply in frequency as the topic emerges. The goal of the present work is to develop a formal approach for modeling such "bursts," in such a way that they can be robustly and efficiently identified, and can provide an organizational framework for analyzing the underlying content. At one level, the approach presented here can be viewed as drawing an analogy with models from queueing theory for bursty network traffic (see e.g. [32]). In addition, however, the analysis of the underlying burst patterns reveals a latent hierarchical structure that often has a natural meaning in terms of the content of the stream. My initial aim in studying this issue was a very concrete one: I wanted a better organizing principle for the enormous archives of personal e-mail that I was accumulating. Abundant anecdotal evidence, as well as academic research [6, 42, 59], suggested that my own experience with "e-mail overload" corresponded to a near-universal phenomenon -- a consequence of both the rate at which e-mail arrives, and the demands of managing volumes of saved personal correspondence that can easily grow into tens and hundreds of megabytes of pure text content. And at a still larger scale, e-mail has become the raw material for legal proceedings [34] and historical investigation [8, 38, 44] -- with the National Archives, for example, agreeing to accept tens of millions of e-mail messages from the Clinton White House [45]. In sum, there are several settings where it is a crucial problem to find structures that can help in making sense of large volumes of e-mail. An active line of research has applied text indexing and classification to develop e-mail interfaces that organize incoming messages into folders on specific topics, sometimes recommending further actions on the part of a user [4, 9, 13, 29, 30, 39, 46, 47, 49, 50, 51, 53, 54] -- in effect, this framework seeks to automate a kind of filing system that many users implement manually. There has also been work on developing query interfaces to fully-indexed collections of e-mail [7]. My interest here is in exploring organizing structures based more explicitly on the role of time in e-mail and other document streams. Indeed, even the flow of a single focused topic 2. is modulated by the rate at which relevant messages or documents arrive, dividing naturally into more localized episodes that correspond to bursts of activity of the type suggested above. For example, my saved e-mail contains over a thousand messages relevant to the topic "grant proposals" -- announcements of new funding programs, planning of proposals, and correspondence with co-authors. While one could divide this collection into sub-topics based on message content -- certain people, programs, or funding agencies form the topics of some messages but not others -- an equally natural and substantially orthogonal organization for this topic would take into account the sequence of episodes reflected in the set of messages -- bursts that surround the planning and writing of certain proposals. Indeed, certain subtopics (e.g. "the process of gathering people together for our large NSF ITR proposal") may be much more easily characterized by a sudden confluence of message-sending over a particular period of time than by textual features of the messages themselves. One can easily argue that many of the large topics represented in a document stream are naturally punctuated by bursts in this way, with the flow of relevant items intensifying in certain key periods. A general technique for highlighting these bursts thus has the potential to expose a great deal of fine-grained structure. Before moving to a more technical overview of the methodology, let me suggest one further perspective on this issue, quite distant from computational concerns. If one were to view a particular folder of e-mail not simply as a document stream but also as something akin to a narrative that unfolds over time, then one immediately brings into play a body of work that deals explicitly with the bursty nature of time in narratives, and the way in which particular events are signaled by a compression of the time-sense. In an early concrete reference to this idea, E.M. Forster, lecturing on the structure of the novel in the 1920's, asserted that . . . there seems something else in life besides time, something which may conveniently be called "value," something which is measured not by minutes or hours but by intensity, so that when we look at our past it does not stretch back evenly but piles up into a few notable pinnacles, and when we look at the future it seems sometimes a wall, sometimes a cloud, sometimes a sun, but never a chronological chart [17]. This role of time in narratives is developed more explicitly in work of Genette [19, 20], Chatman [11], and others on anisochronies, the non-uniform relationships between the amount of time spanned by a story's events and the amount of time devoted to these events in the actual telling of the story. Modeling Bursty Streams. Suppose we were presented with a document stream -- for concreteness, consider a large folder of e-mail on a single broad topic. How should we go about identifying the main bursts of activity, and how do they help impose additional structure on the stream? The basic point emerging from the discussion above is that such 3. bursts correspond roughly to points at which the intensity of message arrivals increases sharply, perhaps from once every few weeks or days to once every few hours or minutes. But the rate of arrivals is in general very "rugged": it does not typically rise smoothly to a crescendo and then fall away, but rather exhibits frequent alternations of rapid flurries and longer pauses in close proximity. Thus, methods that analyze gaps between consecutive message arrivals in too simplistic a way can easily be pulled into identifying large numbers of short spurious bursts, as well as fragmenting long bursts into many smaller ones. Moreover, a simple enumeration of close-together sets of messages is only a first step toward more intricate structure. The broader goal is thus to extract global structure from a robust kind of data reduction -- identifying bursts only when they have sufficient intensity, and in a way that allows a burst to persist smoothly across a fairly non-uniform pattern of message arrivals. My approach here is to model the stream using an infinite-state automaton A, which at any point in time can be in one of an underlying set of states, and emits messages at different rates depending on its state. Specifically, the automaton A has a set of states that correspond to increasingly rapid rates of emission, and the onset of a burst is signaled by a state transition -- from a lower state to a higher state. By assigning costs to state transitions, one can control the frequency of such transitions, preventing very short bursts and making it easier to identify long bursts despite transient changes in the rate of the stream. The overall framework is developed in Section 2. It can be viewed as drawing an analogy to the use of on-off Markov sources in modeling bursty network traffic (see for example the overview article by Kelly [32]), as well as drawing on the formalism of hidden Markov models [48]. Using an automaton with states that correspond to higher and higher intensities provides an additional source of analytical leverage -- the bursts associated with state transitions form a naturally nested structure, with a long burst of low intensity potentially containing several bursts of higher intensity inside it (and so on, recursively). For a folder of related e-mail messages, we will see in Sections 2 and 3 that this can provide a hierarchical decomposition of the temporal order, with long-running episodes intensifying into briefer ones according to a natural tree structure. This tree can thus be viewed as imposing a fine-grained organization on the sub-episodes within the message stream. Following this development, Section 4 focuses on a case in which the document stream is comprised not of e-mail messages but of computer science conference paper titles over the past several decades; the set of bursts in this stream corresponds roughly to the appearance and disappearance of certain terms of interest in the papers. Section 5 discusses the connections to related work in a range of areas, particularly the striking recent work of Swan, Allan, and Jensen [56, 57, 58] on overview timelines, which forms the body of research closest to the approach here. Finally, Section 6 discusses some further applications of the methodology -- how burstiness in arrivals can help to identify certain messages as "landmarks" in a large corpus of e-mail; and how the overall framework can be applied to logs of Web traffic. 4. 2 A Weighted Automaton Model Perhaps the simplest randomized model for generating a sequence of message arrival times is based on an exponential distribution: messages are emitted in a probabilistic manner, so that the gap x in time between messages i and i + 1 is distributed according to the "memoryless" exponential density function f (x) = ffe-ffx, for a parameter ff > 0. (In other words, the probability that the gap exceeds x is equal to e-ffx.) The expected value of the gap in this model is ff-1, and hence one can refer to ff as the rate of message arrivals. Intuitively, a "bursty" model should extend this simple formulation by exhibiting periods of lower rate interleaved with periods of higher rate. A natural way to do this is to construct a model with multiple states, where the rate depends on the current state. Let us start with a basic model that incorporates this idea, and then extend it to the models that will primarily be used in what follows. A two-state model. Arguably the most basic bursty model of this type would be constructed from a probabilistic automaton A with two states q0 and q1, which we can think of as corresponding to "low" and "high." When A is in state q0, messages are emitted at a slow rate, with gaps x between consecutive messages distributed independently according to a density function f0(x) = ff0e-ff0x When A is in state q1, messages are emitted at a faster rate, with gaps distributed independently according to f1(x) = ff1e-ff1x, where ff1 > ff0. Finally, between messages, A changes state with probability p 2 (0, 1), remaining in its current state with probability 1 - p, independently of previous emissions and state changes. Such a model could be used to generate a sequence of messages in the natural way. A begins in state q0. Before each message (including the first) is emitted, A changes state with probability p. A message is then emitted, and the gap in time until the next message is determined by the distribution associated with A's current state. One can apply this generative model to find a likely state sequence, given a set of messages. Suppose there is a given set of n + 1 messages, with specified arrival times; this determines a sequence of n inter-arrival gaps x = (x1, x2, . . . , xn). The development here will use the basic assumption that all gaps xi are strictly positive. We can use the Bayes procedure (as in e.g. [14]) to determine the conditional probability of a state sequence q = (qi1, . . . , qin); note that this must be done in terms of the underlying density functions, since the gaps are not drawn from discrete distributions. Each state sequence q induces a density function fq over sequences of gaps, which has the form fq(x1, . . . , xn) = Qnt=1 fit(xt). If b denotes the number of state transitions in the sequence q -- that is, the number of indices it so that qit 6= qit+1 -- then the (prior) probability of q is equal to ( Y it6=it+1 p)( Yit=it+1 1 - p) = p b(1 - p)n-b = p 1 - p ! b (1 - p)n. 5. (In this calculation, let i0 = 0, since A starts in state q0.) Now, Pr [q | x] = Pr [q] fq(x)P q0 Pr [q0] fq0 (x) = 1Z p1 - p ! b (1 - p)n nY t=1 f it(xt), where Z is the normalizing constant Pq0 Pr [q0] fq0 (x). Finding a state sequence q maximizing this probability is equivalent to finding one that minimizes - ln Pr [q | x] = b ln 1 - pp ! + nX t=1 - ln f it(xt)! - n ln(1 - p) + ln Z. Since the third and fourth terms are independent of the state sequence, this latter optimization problem is equivalent to finding a state sequence q that minimizes the following cost function: c (q | x) = b ln 1 - pp ! + nX t=1 - ln f it (xt)! Finding a state sequence to minimize this cost function is a problem that can be motivated intuitively on its own terms, without recourse to the underlying probabilistic model. The first of the two terms in the expression for c (q | x) favors sequences with a small number of state transitions, while the second term favors state sequences that conform well to the sequence x of gap values. Thus, one expects the optimum to track the global structure of bursts in the gap sequence, while holding to a single state through local periods of non-uniformity. Varying the coefficient on b controls the amount of "inertia" fixing the automaton in its current state. The next step is to extend this simple "high-low" model to one with a richer state set, using a cost model; this will lead to a method that also extracts hierarchical structure from the pattern of bursts. An infinite-state model. Consider a sequence of n + 1 messages that arrive over a period of time of length T . If the messages were spaced completely evenly over this time interval, then they would arrive with gaps of size g = T /n. Bursts of greater and greater intensity would be associated with gaps smaller and smaller than g. This suggests focusing on an infinite-state automaton whose states correspond to gap sizes that may be arbitrarily small, so as to capture the full range of possible bursts. The development here will use a cost model as in the two-state case, where the underlying goal is to find a state sequence of minimum cost.
Thus, consider an automaton with a "base state" q0 that has an associated exponential density function f0 with rate ff0 = g-1 = n/T -- consistent with completely uniform message arrivals. For each i > 0, there is a state qi with associated exponential density fi having
6.
0 1 32
g ln n per state
20 1 3 tree representation
0 1 32 bursts
b)
time
optimal state sequence
a) q q q q0 1 2 3 qi
transition cost transition cost 0 emissions at rateg-1 s i
Figure 1: An infinite-state model for bursty sequences. (a) The infinite-state automaton A*s,fl; in state qi, messages are emitted at a spacing in time that is distributed according to f(x) = ffie-ffix, where ffi = g-1si. There is a cost to move to states of higher index, but not to states of lower index. (b) Given a sequence of gaps between message arrivals, an optimal state sequence in A*s,fl is computed. This gives rise to a set of nested bursts: intervals of time in which the optimal state has at least a certain index. The inclusions among the set of bursts can be naturally represented by a tree structure.
rate ffi = g-1si, where s > 1 is a scaling parameter. (i will be referred to as the index of the state qi.) In other words, the infinite sequence of states q0, q1, . . . models inter-arrival gaps that decrease geometrically from g; there is an expected rate of message arrivals that intensifies for larger and larger values of i. Finally, for every i and j, there is a cost o/ (i, j) associated with a state transition from qi to qj. The framework allows considerable flexibility in formulating the cost function; for the work described here, o/ (*, *) is defined so that the cost of moving from a lower-intensity burst state to a higher-intensity one is proportional to the number of intervening states, but there is no cost for the automaton to end a higher-intensity burst and drop down to a lower-intensity one. Specifically, when j > i, moving from qi to qj incurs a cost of (j - i)fl ln n, where fl > 0 is a parameter; and when j 0, since all gaps are positive.) If q* is an optimal state sequence in Aks,fl, then it is also an optimal state sequence in A*s,fl .
Before proceeding to the proof, here are two key points to note. First, in all the experiments here, an optimal state sequence in A*s,fl can be found by restricting to a number of states k that is a very small constant, always at most 25.
Second, some condition requiring gaps to be positive is necessary in order for the theorem to hold, as the following example shows. Suppose that x were to consist of n gaps, each equal to 0, where n is large enough that sn > nfl . Then the state sequence q(j) in which all n states are equal to qj has cost
c iq(j) | xj = j(fl ln n) - n ln fj(0) = j(fl ln n) - n ln ffj
= j(fl ln n) - nj ln s + n ln g = j(fl ln n - n ln s) + n ln g.
8.
For increasing values of j, these costs c iq(j) | xj form a sequence of negative numbers tending to -1, and hence there is no state sequence in A*s,fl that achieves a cost less than or equal to that of all others.
When all gaps are positive, however, no such example is possible, since Theorem 2.1 establishes that there is a state sequence in A*s,fl achieving the minimum cost.
Proof of Theorem 2.1. Let q* = (q`1 , . . . , q`n) be an optimal state sequence in Aks,fl, and let q = (qi1, . . . , qin) be an arbitrary state sequence in A*s,fl. As always, set `0 = i0 = 0, since both sequences start in state q0; for notational purposes, it is useful to define `n+1 = in+1 = 0 as well. The goal is to show that c (q* | x) = j0 >= j* + 1, then - ln fj00 (xt) >= - ln fj0 (x).
Since k = d1 + logs T + logs ffi(x)-1e, one has
ffk-1 = g-1sk-1 = nT * sk-1 >= 1T * slogs T +logs ffi(x)-
1 = 1
T
T ffi(x) =
1 ffi(x).
Since ffi(x)-1 >= x-1t for any t = 1, 2, . . . , n, the index k - 1 is at least as large as the j for which - ln fj(xt) is minimized. It follows that for those t for which it 6= it0 one has-
ln fi0t(xt) it0 = k - 1.
Combining these inequalities for the state transition costs and the gap costs, one obtains
c (q0 | x) =
n-1X
t=0 o/ (i
0t, i0t+1)!+ nX
t=1 - ln f
i0t(xt)! 0.
Note that although the final computation of an optimal state sequence is carried out by recourse to a finite-state model, working with the infinite model has the advantage that a number of states k is not fixed a priori; rather, it emerges in the course of the computation, and in this way the automaton A*s,fl essentially "conforms" to the particular input instance.
3 Hierarchical Structure and E-mail Streams Extracting hierarchical structure. From an algorithm to compute an optimal state sequence, one can then define the basic representation of a set of bursts, according to a hierarchical structure.
For a set of messages generating a sequence of positive inter-arrival gaps x = (x1, x2, . . . , xn), suppose that an optimal state sequence q = (qi1, qi2, . . . , qin) in A*s,fl has been determined. Following the discussion of the previous section, we can formally define a burst of intensity j to be a maximal interval over which q is in a state of index j or higher. More precisely, it is an interval [t, t0] so that it, . . . , it0 >= j but it-1 and it0+1 are less than j (or undefined if t - 1 n).
It follows that bursts exhibit a natural nested structure: a burst of intensity j may contain one or more sub-intervals that are bursts of intensity j + 1; these in turn may contain subintervals that are bursts of intensity j + 2; and so forth. This relationship can be represented by a rooted tree \Gamma , as follows. There is a node corresponding to each burst; and node v is a child of node u if node u represents a burst Bu of intensity j (for some value of j), and node v represents a burst Bv of intensity j + 1 such that Bv ` Bu. Note that the root of \Gamma corresponds to the single burst of intensity 0, which is equal to the whole interval [0, n].
Thus, the tree \Gamma captures hierarchical structure that is implicit in the underlying stream. Figure 1(b) shows the transformation from an optimal state sequence, to a set of nested bursts, to a tree.
Hierarchy in an e-mail stream. Let us now return to one of the initial motivations for this model, and consider a stream of e-mail messages. What does the hierarchical structure of bursts look like in this setting?
I applied the algorithm to my own collection of saved e-mail, consisting of messages sent and received between June 9, 1997 and August 23, 2001. (The cut-off date is chosen here so as to roughly cover four academic years.) First, here is a brief summary of this collection. Every piece of mail I sent or received during this period of time, using my cs.cornell.edu email address, can be viewed as belonging to one of two categories: first, messages consisting of one or more large files, such as drafts of papers mailed between co-authors (essentially, e-mail as file transfer); and second, all other messages. The collection I am considering here consists simply of all messages belonging to the second, much larger category; thus, to a
10.
rough approximation, it is all the mail I sent and received during this period, unfiltered by content but excluding long files. It contains 34344 messages in UNIX mailbox format, totaling 41.7 megabytes of ascii text, excluding message headers.1
Subsets of the collection can be chosen by selecting all messages that contain a particular string or set of strings; this can be viewed as an analogue of a "folder" of related messages, although messages in the present case are related not because they were manually filed together but because they are the response set to a particular query. Studying the stream induced by such a response set raises two distinct but related questions. First, is it in fact the case that the appearance of messages containing particular words exhibits a "spike," in some informal sense, in the (temporal) vicinity of significant times such as deadlines, scheduled events, or unexpected developments? And second, do the algorithms developed here provide a means for identifying this phenomenon?
In fact such spikes appear to be quite prevalent, and also rich enough that the algorithms of the previous section can extract hierarchical structure that in many cases is quite deep. Moreover, the algorithms are efficient enough that computing a representation for the bursts on a query to the full e-mail collection can be done in real-time, using a simple implementation on a standard PC.
To give a qualitative sense for the kind of structure one obtains, Figures 2 and 3 show the results of computing bursts for two different queries using the automaton A*2. Figure 2 shows an analysis of the stream of all messages containing the word "ITR," which is prominent in my e-mail because it is the name of a large National Science Foundation program for which my colleagues and I wrote two proposals in 1999-2000. There are many possible ways to organize this stream of messages, but one general backdrop against which to view the stream is the set of deadlines imposed by the NSF for the first run of the program. Large proposals were submitted in a three-phase process, with deadlines of 11/15/99, 1/5/00, and 4/17/00 for letters of intent, pre-proposals, and full proposals respectively. Small proposals were submitted in a two-phase process, with deadlines of 1/5/00 and 2/14/00 for letters of intent and full proposals respectively. I participated in a group writing a proposal of each kind.
Turning to the figure, part (a) is a plot of the raw input to the automaton A*2, showing the arrival time of each message in the response set. Part (b) shows a nested interval representation of the set of bursts for the optimal state sequence in A*2; the intervals are annotated with the first and last dates of the messages they contain, and the dates of the NSF deadlines are lined up with the intervals that contain them. Note that this is a schematic representation, designed to show the inclusions that give rise to the tree \Gamma ; the lengths and centering of the intervals in the drawing are not significant. Part (c) shows a drawing of the resulting tree \Gamma . The root corresponds to the single burst of intensity 0 that is present in any state sequence. One sees that the two children of the root span intervals surrounding the
1These figures reveal that I receive less e-mail per day than many of my colleagues; one contributing factor is that I do not subscribe to any high-volume mailing lists based outside Cornell.
11.
2/1410/28-2/21/0010/28/99-
11/1610/28- 11/1611/2- 11/15
11/9-
7/10/00-10/31/00 7/10-7/14
1/2-2/4 1/2-1/5
0 20 40 60 80 100 120 140
1.4e+06 1.5e+06 1.6e+06 1.7e+06 1.8e+06 1.9e+06 2e+06 2.1e+06 2.2e+06 2.3e+06 2.4e+06 2.5e+06 a)
c)
Minutes since 1/1/97
Message #
b)
2/14
10/28 11/16 1/2/00
11/16 11/15
11/2 11/9
2/4 7/10
2/21
7/10
7/14 10/31
10/28/9910/28
(large proposals) 11/15: letter of intent deadline
2/14: full proposal deadline
0 1 2 3 4 5
1/2 1/5
1/5: pre-proposal deadline (large proposals)
4/17: full proposal deadline(large proposals)
7/11: unofficial notification
9/13: official announcementof awards
intensities
(small proposals) (small proposal)
Figure 2: The stream of all messages containing the word "ITR," analyzed using the automaton A*2. (a) The raw input data: the x-axis shows message arrival time; the y-axis shows message sequence number. (b) The set of bursts in the optimal state sequence for A*2, drawn schematically to show the inclusions that form the tree \Gamma . (Lengths of intervals are standardized and hence not to scale.) Intervals are annotated with starting and ending dates, and the dates of the NSF ITR program deadlines are lined up with the intervals that contain them. (c) A representation of the tree \Gamma , showing inclusions among the bursts.
submission deadlines and notification dates, respectively. Moreover, the sub-tree rooted at the first of these children splits further into two sub-trees that are concentrated over a week leading up to the deadline for letters of intent (11/15/99), and four days leading up to the pre-proposal deadline (1/5/00). Finally, note that there is no burst of positive intensity over the final deadline for large proposal, since we did not continue our large submission past the pre-proposal stage.
Figure 3 shows an analysis of the stream of all messages containing the word "prelim," which is the term used at Cornell for (non-final) exams in undergraduate courses. One sees that the raw data in this example (part (a) of the figure) exhibits an arguably more regular structure than in the previous example. I taught undergraduate courses in four of the eight semesters covered by the collection of e-mail, and each of these courses had two prelims.
12.
prelim 24/11/00 prelim 12/24/00 prelim 24/15/99 prelim 12/25/99
11/13/00prelim 2
1 2 3 40 5 6 7 8
prelim 110/4/00 intensities 0 50 100 150 200 250 300 350 400
200000 400000 600000 800000 1e+06 1.2e+06 1.4e+06 1.6e+06 1.8e+06 2e+06 2.2e+06 2.4e+06
Minutes since 1/1/97
Message #
a)
c)
b)
Figure 3: The stream of all messages containing the word "prelim," analyzed using the automaton A*2. Parts (a), (b), and (c) are analogous to Figure 2, but date annotations are omitted. In part (b), the dates of prelims (exams) are lined up with the intervals that contain them.
For the first of these courses, correspondence with students was restricted almost exclusively to a special course e-mail account, and hence very little appears in my own saved e-mail. The remaining three courses are captured very cleanly by the tree \Gamma computed from the optimal state sequence of A*2 (parts (b) and (c) of the figure) -- each course corresponds to a long burst, and each contains two shorter, more intense bursts for the particular prelims. Specifically, the three children of the root are centered over the semesters in which the three undergraduate courses were taught (Spring 1999, Spring 2000, and Fall 2000); and the subtrees below these children split further into two sub-trees each, concentrated either directly over or slightly preceding the two prelims given that semester.
Overall, these structures suggest how a large folder of e-mail might naturally be divided into a hierarchical set of sub-folders around certain key events, based only on the rate of message arrivals. The appropriateness of Forster's comments on the time-sense in narratives is also fairly striking here: when organized by burst intensities, the period of time covered
13.
in the e-mail collection very clearly "piles up into a few notable pinnacles" [17], rather than proceeding uniformly.
4 Enumerating Bursts Given a framework for identifying bursts, it becomes possible to perform a type of enumeration: for every word w that appears in the collection, one computes all the bursts in the stream of messages containing w. Combined with a method for computing a weight associated with each burst, and for then ranking by weight, this essentially provides a way to find the terms that exhibit the most prominent rising and falling pattern over a limited period of time. This can be applied to e-mail, and it can be done very efficiently even on the scale of the e-mail corpus from the previous section; roughly speaking, it can be performed in a single pass over an inverted index for the collection. Here, however, I consider a different application of this technique: extracting bursts in term usage from the titles of conference papers. Two distinct sources of data will be used here: the titles of all papers from the database conferences SIGMOD and VLDB for the years 1975-2001; and the titles of all papers from the theory conferences STOC and FOCS for the years 1969-2001.
The first issue that must be addressed concerns the underlying model: unlike e-mail messages, which arrive continuously over time, conference papers appear in large batches -- essentially, twenty to sixty new papers appear together every half year. As a result, the automaton A*s,fl is not appropriate, since it is fundamentally based on analyzing the distribution of inter-arrival gaps. Instead, one needs to model a related kind of phenomenon: documents arrive in discrete batches; in each new batch of documents, some are relevant (in the present case, their titles contain a particular word w) and some are irrelevant. The idea is thus to find an automaton model that generates batched arrivals, with particular fractions of relevant documents. A sequence of batched arrivals could be considered bursty if the fraction of relevant documents alternates between reasonably long periods in which the fraction is small and other periods in which it is large.
Suppose there are n batches of documents; the tth batch contains rt relevant documents out of a total of dt. Let R = Pnt=1 rt and D = Pnt=1 dt. Now, define an automaton B*s,fl as follows, by close analogy with the construction of A*s,fl. For each state qi of B*s,fl , for i >= 0, there is an expected fraction of relevant documents pi. Set p0 = p = R/D, and pi = p0si. Since it does not make sense for pi to exceed 1, the state qi will only be defined for i such that pi = 1; thus, B*s,fl will be a finite-state automaton. One can further restrict B*s,fl to k states, resulting in the automaton Bks,fl. Viewed in a generative fashion, one can imagine state qi in these models as producing a mixture of relevant and irrelevant documents according to a binomial distribution with probability pi.
The cost of a state sequence q = (qi1, . . . , qin) in B*s,fl is defined as follows. If the automa14.
Word Interval of burst data 1975 SIGMOD -- 1979 SIGMOD base 1975 SIGMOD -- 1981 VLDB application 1975 SIGMOD -- 1982 SIGMOD bases 1975 SIGMOD -- 1982 VLDB design 1975 SIGMOD -- 1985 VLDB relational 1975 SIGMOD -- 1989 VLDB model 1975 SIGMOD -- 1992 VLDB large 1975 VLDB -- 1977 VLDB schema 1975 VLDB -- 1980 VLDB theory 1977 VLDB -- 1984 SIGMOD distributed 1977 VLDB -- 1985 SIGMOD data 1980 VLDB -- 1981 VLDB statistical 1981 VLDB -- 1984 VLDB database 1982 SIGMOD -- 1987 VLDB nested 1984 VLDB -- 1991 VLDB deductive 1985 VLDB -- 1994 VLDB transaction 1987 SIGMOD -- 1992 SIGMOD objects 1987 VLDB -- 1992 SIGMOD object-oriented 1987 SIGMOD -- 1994 VLDB parallel 1989 VLDB -- 1996 VLDB object 1990 SIGMOD -- 1996 VLDB mining 1995 VLDB -- server 1996 SIGMOD -- 2000 VLDB sql 1996 VLDB -- 2000 VLDB warehouse 1996 VLDB -- similarity 1997 SIGMOD -- approximate 1997 VLDB -- web 1998 SIGMOD -- indexing 1999 SIGMOD -- xml 1999 VLDB --
Figure 4: The 30 bursts of highest weight in B22, using titles of all papers from the database conferences SIGMOD and VLDB, 1975-2001.
ton is in state qi when the tth batch arrives, a cost of
oe(i, t) = - ln "dtr
t!p
rti (1 - pi)dt-rt#
is incurred, since this is the negative logarithm of the probability that rt relevant documents would be generated using a binomial distribution with probability pi. There is also a cost of o/ (it, it+1) associated with the state transition from qit to qit+1 , where this cost is defined precisely as for A*s,fl. A state sequence of minimum total cost can then be computed as in Section 2.
In the analysis of conference paper titles here, the main goal is to enumerate bursts of
15.
Word Interval of burst grammars 1969 STOC -- 1973 FOCS automata 1969 STOC -- 1974 STOC languages 1969 STOC -- 1977 STOC machines 1969 STOC -- 1978 STOC recursive 1969 STOC -- 1979 FOCS classes 1969 STOC -- 1981 FOCS some 1969 STOC -- 1980 FOCS sequential 1969 FOCS -- 1972 FOCS equivalence 1969 FOCS -- 1981 FOCS programs 1969 FOCS -- 1986 FOCS program 1970 FOCS -- 1978 STOC on 1973 FOCS -- 1976 STOC complexity 1974 STOC -- 1975 FOCS problems 1975 FOCS -- 1976 FOCS relational 1975 FOCS -- 1982 FOCS logic 1976 FOCS -- 1984 STOC vlsi 1980 FOCS -- 1986 STOC probabilistic 1981 FOCS -- 1986 FOCS how 1982 STOC -- 1988 STOC parallel 1984 STOC -- 1987 FOCS algorithm 1984 FOCS -- 1987 FOCS graphs 1987 STOC -- 1989 STOC learning 1987 FOCS -- 1997 FOCS competitive 1990 FOCS -- 1994 FOCS randomized 1992 STOC -- 1995 STOC approximation 1993 STOC -- improved 1994 STOC -- 2000 STOC codes 1994 FOCS -- approximating 1995 FOCS -- quantum 1996 FOCS --
Figure 5: The 30 bursts of highest weight in B22, using titles of all papers from the theory conferences STOC and FOCS, 1969-2001.
positive intensity, but not to emphasize hierarchical structure. Thus, the two-state automaton B22 is used; given an optimal state sequence, bursts of positive intensity correspond to intervals in which the state is q1 rather than q0. For such a burst [t1, t2], we can define the weight of the burst to be
t2X
t=t1(oe(0, t) - oe(1, t)). In other words, the weight is equal to the improvement in cost incurred by using state 1 over the interval rather than state 0. Observe that in an optimal sequence, the weight of every burst is non-negative. Intuitively, then, bursts of larger weight correspond to more prominent periods of elevated activity. (This notion of weight can be naturally extended to
16.
larger numbers of states, as well as to the automaton model from Section 2.)
In Figure 4, this framework is applied to the titles of SIGMOD and VLDB papers for the years 1975-2001. For each word w (including stop-words), an input to B22 is constructed in which rt is the number of titles at the tth conference (chronologically) that contain the word w, and dt is the total number of titles at the tth conference. The 30 bursts with the highest weight, over all possible words w, are then depicted in the figure, sorted by year of appearance. The bursts with no given ending date (`mining', `warehouse', `similarity', `approximate', `web', `indexing', and `xml') are those for which the interval extends to the most recent conference, suggesting terms that are in the middle of a large-weight burst at present. Note that no pre-processing is done on the titles, other than to convert each word to lower-case. One observes that the words in Figure 4 are almost all quickly recognizable as carrying technical content, even though they are the top results in an enumeration where bursts were computed and ranked for all words, including stop-words.2
Figure 5 shows the results of the same computation on the titles of STOC and FOCS papers for the years 1969-2001. For both these collections, it is important to note that the number of occurrences of a word w is in general a quantity that, at a local scale, changes very rapidly from one conference to the next; thus, many of the intervals depicted in the figures span conferences in which the indicated word did not appear at all, and omit ones with large numbers of occurrences. The non-trivial cost of state transitions in B22 is crucial in making it possible for intervals of any reasonable length to form in the presence of this data.
5 Related Work The Topic Detection and Tracking (TDT) study [2, 3, 61, 62] articulated the problem of extracting significant topics and events from a stream of news articles, thereby framing the type of document stream analysis questions considered here. Much of the emphasis in the TDT study was on techniques for the on-line version of the problem, in which events must be detected in real-time; but there was also a retrospective version in which the whole stream could be analyzed. Similar issues have recently been addressed in the visualization community [26, 43, 60], where the problem of visualizing the appearance and disappearance of themes in a sequence of news stories has been explored.
Following on the TDT work, Swan, Allan, and Jensen [56, 57, 58] developed a method for constructing overview timelines of a set of news stories. For each named entity and noun phrase in the corpus, they perform a O/2 test to identify days on which the number of occurrences yields a value above a certain threshold; contiguous sets of days meeting this condition are then grouped into an interval that is added to the timeline. Thus, the high-level structure of their approach is parallel to the enumerative method in Section 4. However, the
2The bursts for `data,' `base,' and `bases' in the years 1975-1981 arise in large part from the fact that the term "database" was written as two words in a significant number of the paper titles during this period.
17.
underlying methodology is quite different from the present work in two key respects. First, Swan et al. note that the use of thresholds makes it difficult to construct long intervals of activity for a single feature -- such intervals are often broken apart by brief gaps in which the feature does not occur frequently enough, and subsequent heuristics are needed to piece them together. The present work, by modeling a burst as a state transition with costs, allows for a long interval to naturally persist across such gaps; essentially, in place of thresholds, the optimization problem inherent in finding a minimum-cost state sequence adaptively groups nearby high-intensity intervals together when it is advantageous to do so. Second, the work of Swan et al. does not attempt to infer any type of hierarchical structure in the appearance of a feature.
Lewis and Knowles analyze the dynamics of message-sending over a very short time scale, searching for features that can determine whether one message is a response to another [37]. This is applied to develop robust techniques for identifying threads, a popular metaphor for organizing e-mail and newsgroup postings [15, 22]. In a very different context, Grosz and Sidner develop structural models for discourse as a means of analyzing communication [21]; their use of stack models in particular results in a nested organization that bears an intriguing, though distant, relationship to the nested structure of bursts studied here.
The present work clearly overlaps with the large areas of time series analysis and sequence mining [10, 25]; connections to related probabilistic frameworks such as bursty on-off sources [32] and hidden Markov models [48] have already been discussed above. Ehrich and Foith [16] proposed a method for constructing a tree from a one-dimensional time series, essentially by introducing a branch-point at each local minimum and a leaf at each local maximum (see also [55]). In the context of the applications here, such an approach would yield trees of enormous complexity, due to the ruggedness of the underlying temporal data, with many local minima and maxima.
The search for a minimum-cost state sequence in the automata of Section 2 and 4 can also be viewed as a search for approximate level sets in a time series, and hence related to the large body of work on piece-wise function approximation in both statistics and data mining (see e.g. [23, 24, 27, 31, 33, 35, 41]). In a discrete framework, work on mining episodes and sequential patterns (e.g. [1, 12, 25, 40]) has developed algorithms to identify particular configurations of discrete events clustered in time, in some cases obeying partial precedence constraints on their order. Finally, there is an interesting general relationship to work on traffic analysis in the areas of cryptography and security [52]; in that context, temporal analysis of a message stream is crucial because the content of the messages has been explicitly obscured.
6 Extensions and Conclusions In the settings discussed above, the analysis has made use of both the temporal information and the underlying content. The role of temporal data is clear; but the content of course
18.
plays an integral role as well: Section 3 deals with streams consisting of the response set for a particular query to a larger stream; and Section 4 considers streams with batched arrivals, in which a particular subset of each batch is designated as relevant. And in fact, there is strong evidence that the interplay between content and time is crucial here -- that an arbitrary set of messages with same sequence of arrival times would not exhibit an equally strong set of bursts. Adapting a permutation test from Swan and Jensen [58], one can start with a complete e-mail corpus having arrival times t1, t2, . . . , tN , choose a random permutation ss, and shuffle the corpus so that message ss(i) arrives at time ti (instead of message i), for i = 1, 2, . . . , N . The resulting shuffled corpus has the same set of arrival times and the same messages, but the original correspondence between the two is broken; do equivalently strong "spurious" bursts appear in this new sequence? In fact, they clearly do not: when the weight of bursts for all words (with respect to A*2) is computed using the e-mail corpus in Section 3, the total weight associated with the true corpus is more than an order of magnitude greater than the average total weight over 100 randomly shuffled versions (369,980 versus 25,141). Moreover, the shuffled versions exhibit almost no non-trivial hierarchical structure; the average total number of words generating bursts of intensity at least 2 (i.e. inducing trees \Gamma with two or more levels below the root) is 16.7 over the randomly shuffled versions, compared with 3865 in the true corpus.
I have also applied the overall framework developed here to Web clickstream data collected by Gay et al. [18]. The dataset in [18] was compiled as part of a study of student usage of wireless laptops: The browser clicks of roughly 80 undergraduate students in two particular classes at Cornell were collected (with consent) from wireless laptops over a period of two and a half months in Spring 2000. Bursts with respect to A*s,fl can be computed by an enumerative method, as in Section 4: for every URL w, all bursts in the stream of visits to w are determined; the full set of bursts is then ordered by weight. Each burst, associated with a URL w, now has an additional quantity associated with it: the number of distinct users who visited w during the interval of the burst. This allows one to distinguish between collective activity involving much of the class and that of just a single user. As it turns out, if one focuses on bursts that involve at least 10 distinct users, then many of those with the highest weight involve the URLs of the on-line class reading assignments, centered on intervals shortly before and during the weekly sessions at which they were discussed.
A final observation is that the use of a model based on state transitions leads to bursts with sharp boundaries; they have clear beginnings and ends. In particular, this means that for every burst, one can identify a single message on which the associated state transition occurred. This is akin to the TDT study's notion of (retrospective) first story detection [2], although in the automaton model of the present work, identifying initial messages does not constitute a separate problem since it follows directly from the definition of the state transitions. In the context of e-mail, the contents of such an initial message can often serve as a concentrated summary of the circumstances precipitating the burst -- in other words, there is frequently something in the message itself to frame the flurry of message19.
sending that is about to occur. And for messages on which bursts for several different terms are initiated simultaneously, this phenomenon is even more apparent; such messages often represent natural "landmarks" at the beginning of a long-running episode.
In many domains, we accumulate extensive and detailed records of our own behavior -- in the e-mail we send and receive, the Web pages we visit, the queries we issue to search engines. An underlying theme, of which several aspects have been developed here, is that a great number of these settings have a fundamental temporal aspect; they are punctuated by the sharp and sudden onset of particular episodes, and can be organized around rising and falling patterns of activity. There is a great amount of complexity underpinning such a picture. But by developing a better understanding of it, one can hope ultimately to find structure in the raw data that we generate through the basic process of interacting and communicating.
Acknowledgements. I thank Lillian Lee for valuable discussions and suggestions throughout the course of this work.
IMAP (Internet Message Access Protocol) was designed to centralize email information, I believe. If stored/implemented with a database, what more would you need ?
I think querying through SQL would satisfy most of us.. and be very useful in corporate environments (for example, query all email sent from a user to support), and it's already done by some projects like DBMAIL.
Anybody out there with experience using these ?
BTW, there's an extensive database of IMAP products including some that make the data accessible via LDAP... hours of fun!
Notepad specialist & FAT administrator, group training available
Now we all now that most email is delivered promptly by gremlins, but gremlins are hungry and will eat a few bytes here and there.
They also leave waste in the form of spam.
So, I propose that we turn to gnomes to deliver the mail instead, as they are much cleaner, and can be satiated by attaching a file like 'Hamburger.txt'.
"I only speak the truth"
Karma: null(Mostly affected by an unassigned variable)
Every time you sign up for some mailing list or discussion group, create a new e-mail account or alias for just those mailings. Bam, it's automatically sorted out by itself with extreme ease. If you have limited bandwith (or are checking, say, on your palm) sometimes, just check your important addresses frequently, and reserve your mailing lists for a once-per-day check.
If some site asks for your e-mail address to download a piece of software, or to register, make up a new alias and give that to them. If you start getting tons of crap at that address, you can just remove that alias, and they get it all bounced back in their stupid spamming faces.
Give one address to your cow-orkers just for work stuff. Give a different one to your Mom and other techno-nots that blocks all attachments. Give another one to your friends with brains that goes unfiltered. For people you don't want to talk to, give them the address of an autoresponder tied to Eliza.
Be a *Happy Camper* and let your addresses be *Bubbles* and you be just *You*.
... "Give me a woman who loves beer and I will conquer the w
there is no thing
what else could you want?
How about plain text, HTML, RTF, or PDF? Every person who's been on the internet longer than two months has Acrobat.
DO NOT DISTURB THE SE
I used to know how to do this, but I forgot it as soon as I figured it out. Go figure...
What was I talking about?
The Dopester
"Yes, I'm a Karma Whore, but I'm doing it to pay my way through school."
Not to mention that a PDF would be 10x the size. I have no idea why Mac and Windows OS's are so baffled by postscript...half the printer drivers have to deal with it already, why not just bundle a damn interpreter with the OS and have a minimal frontend on it for screen viewing?
Karma: Good (despite my invention of the Karma: sig)
Damn you, Admiral Hopper! I've got a huge stack of COBOL listings on my desk that I've got to translate to, of all things, vbscript (damn you, Bill Gates!)
I say could have because it got sucked down the drain in late 2000 with all of the companies that didn't have a damn thing to offer. Lesson #1: make sure your CEO gets along with your venture partner.
No, I'm not bitter. Much.
a nice methods paper, but mr. kleinberg doesn't use any of the free metadata that comes with email and news: to, from, subject.
i use outlook, and cluster my mail by sender... most of the time, that tells me pretty easily whether a given piece of mail is a work email, a personal email or a mailing list. from there, i check the subject line of work emails, just to confirm my categorization of work/humor/administrivia.
i'd want to see a comparison between a metadata-only method (rules and filters on the RFC 822 header) and mr. kleinberg's method before i'd consider using it.
It's more general than e-mail, but in the wearable computing community, there's a little application called Remembrance Agent, written by Bradley Rhodes that many folks use. In terms of stand-alone UI, it's still quite primitive, but that's because it was built around dynamic hooks into Emacs.
I've been playing around with some Java-based wrapper code, to wrap the ra-retrieve executable in a Server and allow clients to access the data via sockets. I have a Java-based client coded up that hooks into the System clipboard, but it's still in alpha-mode. All GPL'd of course, but needs a little time to mature. It's a proof-of-concept, work in progress. :-)
Check out Brad's site for more insight into the work he did and is doing.
--The more you know, the less you know.
Postscript has the best reproduction accuracy for the file size. Assuming it has any kind of figures or equations, the only other reasonable alternatives are dvi and pdf. I've never seen dvi files rendered in a decent amount of time, and pdf is too fat, esp. for a paper linked to by slashdot. :)
Karma: Good (despite my invention of the Karma: sig)
my $pr0n = "adult";
...
my $spam = "viagra";
my $urgent = "penis enlargement";
open (INBOX,/home/mail) or die "Damn! No fun for me:$!\n";
@list = readdir(INBOX);
foreach $ (@list) {
if (-f $spam) {
my $status = unlink($spam);
}
if (-f $pr0n) {
my @MUST_SEE = $pr0n;
next;
}
if (-f $viagra) {
my @RAINY_DAY = $viagra;
next;
}
}
# or something like that
Amen, brother.
Especially considering NeXT used postscript for its internal rendering, you'd think OSX could at least do the same.
OK, it's not a piece of Linux software, but it is a beautful idea:
http://www.creo.com/sixdegrees/
668: Neighbour of the Beast
Vintage computer games and RPG books available. Email me if you're interested.
Here is a PDF version.
Boy could I use the Karma!
Hoo boy. Here we go again. When are you kids going to get it straight?
- Choosing not to listen to somebody is *not* censorship.
- Throwing your mail away before you open it is *not* censorship.
- Choosing not to relay somebody's spam is *not* censorship.
- Choosing not to broadcast somebody's TV program, even if you own a TV network, is *not* censorship.
- Telling a movie producer you won't distribute his/her movie unless he/she makes cuts or changes to the subject matter is *not* censorship.
- Rallying your church group together to burn books is *not* censorship.
- Refusing to sell certain magazines or newspapers, if you own a newsstand, is *not* censorship.
The only way somebody can be truly "censored" is when there is no legal means for that person to get his/her speech/art/etc. produced and disseminated to the pubic. Generally speaking, the only body with that type of power is the government -- because they make the laws.
Everything else is merely an inconvenience. It may piss you off, sure, and you may wish things were different. But you can't force people to support you, encourage you, or fund you if they just don't want to. For example, people in this country (the US) *do* have a right to decide what material constitutes pornography, relative to their local community standards -- and if you don't like it, you are within your rights to move to another town.
"No censorship" does not mean being forced to look at every piece of crap that somebody wants to throw in your face, and god help us if it did.
Breakfast served all day!
Now I can automatically filter my barely-legal porn spam from my anime porn spam. Lets hear it for technology =)
Somewhat to my astonishment when I clicked on the link up popped a box asking me to confirm Postscript Renderer options! I had no idea that I had anything on this box that could read Postscript.
Some minutes of 100% CPU later up pops a PSP window, with the document rendered in a font about five pixels square. Fair enough, I suppose, for what's basically a photograph editing application.
But really, how bizarre, posting something in a low level printer file format. We'll have people posting documents in PCL5 next.
It shouldn't take two months to get ghostscript and ghostview. In fact, it comes with most modern operating systems.
Actually, ghostscript created a PDF about half the size of the .ps file.
-rw-r--r-- 1 kz None 239121 Apr 24 14:13 bhs.pdf
-rw-r--r-- 1 kz None 433678 Apr 24 14:02 bhs.ps
Of course, the PDF is Flate encoded internally, and the ps is a big fluffy text file, so the ps file would compress to well below the PDF size.
I am not your blowing wind, I am the lightning.
First, I sort out mail from the mailingslists I read.
Then, mail from friends, and people I correspond with a lot.
Finally, I have a weighted scoring recipe:
:0 Bh
* -199^0
#Assign an initial value of -199, mail gets filtered, if the score is above 0, at the end of the recipe.
* 50^1 ^(From|To):.*@hotmail.com
* 50^1 ^(From|To):.*@yahoo.com
* 50^1 ^(From|To):.*@aol.com
* 50^1 ^(From|To):.*@msn.com
* 50^1 ^(From|To):.*@excite.com
* 50^1 ^(From|To):.*@netscape.net
* 50^1 ^(From|To):.*@yahoo.co.uk
#Most mail to and from these domains is spam, so score it.
* 100^1 opt-out
* 50^1 opt-in
* 200^1 OTCBB
* 50^1 viagra
* 50^1 zyban
* 50^1 propecia
* 75^1 FREE
* 75^1 GUARANTEED
* 75^1 LEGAL
* 50^2 MILLIONAIRE
* 50^1 100%
#Words I only see in spam.
mail/Trash
This works quite well for me. If any spam gets through, I try to find some words, that I don't get in normal mail, and add them to the scoring.
/Styx
Message rules are very easy to set up and manage. No agents.
If [Jordan|Saudi Arabia|Egpyt|etc] is so pro-Palestine, why don't they simply absorb all the Palestinians?
Thanks for the brilliant point, Mr Anonymous "I'm so lame I won't post as myself" Coward. You win the Slashdot Sophistic Argument of the Day award!
Spam filtering is one possible application of this type of tool, but the more useful involves taking the mail you *do* want, and sorting it into logical buckets. For instance, let's say work on several open source projects, belong to a couple organizations, and have a real-life job. You could toss a filter in your email that scans each incoming message and throws it in the proper bucket. This allows you to logically separate your mail to reduce confusion of each non-overlapping category.
:-)
Procmail only goes so far, it's really only useful for simple header scanning.. I could really see a good scanner utility being a valuable tool. Maybe Google should share some of their technology..
Josh Woodward
-rw-r--r-- 1 phillips cmb 181384 Apr 24 14:59 bhs.ps.gz
And the winner is...gzipped postscript, which needn't be ungzipped before viewing.
Alas, no. Adobe wanted ridiculous prices to license Display PostScript (DPS), the engine that NeXT used in the NEXTSTEP display system. (NeXT is a company. NEXTSTEP is an operating system.)
Given the ridiculous licensing prices, Apple went a different way and created Display PDF for Mac OS X's drawing system.
Ghostscript works just fine, but the lack of DPS is one of the reasons I still keep a NeXT cube on/under my desk.
There should be a moratorium on the use of the apostrophe.
Max V.
NeXTMail/MIME Mail welcome
Why are there so many people complaining about a PS link? The answer is simple: ./ is news for nerds, not for geeks.
So while the average geek keeps his favorite postscript viewer handy, the standart nerd wonders about such an ancient format and does not know how to feed his acrobat viewer with it...
Here is the solution for those irritated ones: try this piece of ancient software on the ancient adobe format, and you can miracously view it's contents!
Have fun and keep your google handy!
I get alot of spam mail still... I was wondering if Hotmail could ever creat MD5 sums of every e-mail and keep a database, then create some kind of popularity grid where you could, for instance, say hey i don't want e-mail that everyone else is getting...
*shrug* maybe it'd work, maybe not... i'm just tired of getting spam..
I have enjoyed using the VM module for Emacs. It allows sorting your entire Inbox into separate categorized mail boxes via regular expressions. Basically with one shift-A keystroke, my entire day's worth of mailing list stuff gets whisked away into a half-dozen different files. After this, I feel really sorry for people trapped in the Outlook dungeons!
Healthcare article at Kuro5hin
For those without postscript readers, a PDF version is available here.
I'd just like a way to reorganize the emails without affecting them, so that it acts more or less like a database report allowing me to group based on different criteria. For example, if I normally manually organize my emails into separate folders by Topic:Region (where each topic is arising), I'd like to be able to reorganize them by Region:Topic for a different perspective (what's going on in each region).
Check out Enfish Onespace for those of you running MS Outlook. Not only does it do great text mining of all e-mails, it does the same with contacts and with files on your hard drive (the professional version handles network files, as well).
:)
It's got a clean UI, but it is a bit hard getting used to. I've found it to be a great tool for finding info in a snap - I just enter a search phrase and instantly get a list of relevant e-mails, Word docs, spreadsheets, contacts, and even websites.
And nope, I'm not associated with them in any way - I just like the product.
--
Welcome to the land of the easily amused...
I also use this technique for my externally hosted domain...I get all the mail addressed to any user in the domain, but its easy to set up mail client filters to remove those with are addressed To:, say, potentialspammer1@mydomain.
So, if there's any possibility of SPAM, I just invent a new user. Unfortunately, I didn't figure this out quite soon enough and I have some users which get spam and real mail, which I can't afford to filter to trash - people buying their own domains (come on, its like $15 a year) should be thinking ahead.
Also, its not as neat a set up as having my own POP server bounce back the message (which might mean you get off the spam list one day!). More importantly, filtering the To: field, doesn't help me most times, since spammers set the To: to "READTHIS" and use Bcc: for their spammies (is that a word!).
ALSO
Here's an unrelated question for anyone else who owns a domain like me, where they get a catch all POP box.
How do you guys make sure people USE your nice domain name?
In other words, its okay having a POP box, mail.mydomain.com, but you never seem to get offered the services of an SMTP server through which you can send your messages From: this nice address.
I would hazard that most people rely on Reply-To:, which is all very well, except that not all mail clients respect it, and you may want to entirely obscure the actual From:.
Of course, mail clients like Emacs and Mozilla make it easy to arbitrarily set your From:, however you then have to get this through whatever SMTP server you have available (and in order to block spammers and other pranksters, you will increasingly find that most will only send mail if the From: agrees with your user name).
One of the reasons I moved to linux was so I could run sendmail and not rely on other peoples SMTP servers. The is okay at work, since we have direct internet access, but from home when I dial up, it doesn't work.
I don't think my ISP likes to have people sending mail from their own computers, I get name resolution errors from sendmail when attempting to send email (but have no problem with DNS for web), so I think that perhaps the ISPs DNS servers refuse to give up MX records.
Anyone else in a similar boat?
Just use GhostView...
Here ya go, in PDF format: http://www.kevindustries.com/bhs.pdf
ps2pdf bhs.ps worked fine for me...
------
Random, useless fact: I type in startx entirely with my left hand.
What is the difference between postscript and DPS? Any reason why DPS can't be integrated into X? The only effects of a DPDF renderer in OS X that I've seen are being able to view .pdf's without Acrobat and having vector-based widgets.
Karma: Good (despite my invention of the Karma: sig)
I've often thought it would be great if I could save my email to a mysql (or postgres, if you prefer) that would automatically parse the header and body into table fields. Then when you want to search it you can use SQL queries instead of the covoluted grep commands I use now.
Doesn't seem hard to write. Anybody know of such a thing?
"Perhaps even one of them Perl monkeys will quickly hack such a background tool."
Been done already. Check out Mail::Miner.
Matt. Want XML + Apache + Stylesheets? Get AxKit.
NM, here is this project that seems to be just that. Apparently Display Ghostscript is dead, but DPS lives on. Still don't see what the big whoop is.
Karma: Good (despite my invention of the Karma: sig)
Have you seen that http://homepage.mac.com/zoe_info/
My reaction was to want an e-mail reading program that didn't require any filter configuration, though I imagined it would do well to be given a few hints, such as who my boss is, who my mother is, and who my wife is. Other than that, let the program figure it out.
Imagine the canonical, old-fashioned secretary temp. She ('cause that's what the canonical version was) didn't have to know anything domain-specific to sort the morning mail. Magazines go together, bills go together, personal letters go together, etc.
I imagine an automated version for my e-mail. Look at who it is "to" (am I on the list?), look at who is "cc"-ed (am I on that list?), look at who it is from (my boss, wife, or mother?), look at who else it is to (boss, wife, or mother?), look at the thread it is part of (is it responding to something I previously wrote?), look at the content (does it mention me, things I have written, my boss, wife, or mother?). Was it sent to a mailing list? Was it written by someone I have explicitly written to (once or many times?)? Was it written by someone who has previously sent me direct e-mail (once or many times?)? Those ideas are just the obvious ones, think of others. Think of more. (Does it talk about sex, credit card merchant accounts, stock tips, or Nigerian money?)
Now take that and sort it by importance and similarity. Look for a way to present me in a descriptive summary, arranged in a hierarchy with a top-level of, say, 3 to 9 categories, a greatest depth no greater than, say, 4, and keep the sub-branching at intermediate nodes between 3 and 5--but don't max out all those dimensions at once, try to keep the total number of leaf categories to under, say, two dozen. Try to make more important items land higher in the tree and with few siblings, grouped with siblings of similar importance. (Maybe give an importance weight to each e-mail and balance the tree on that scale, that would float e-mails to me from my boss about my mother and wife really high with few siblings.)
This summary needs to be integrated with a complete index of the e-mail so I can see how a message fits into a larger thread, how it fits into previous e-mails.
I (the user) would need to tell the program when to make me a summary of my e-mail (e-mail reading is different when a lot comes in or just a little), and I want to be able to browse through old summaries, including deciding to see composite summaries or, say, the last several days, a week (or three), month, year, or 400 days.
So I think it ends up being a 4-part user interface:
List of summaries (which can be manipulated).
A given summary.
Exhaustive thread/date/subject/sender list (analogous to what every e-mail reader seems to have now). Note that this view could effectively be turned into an exhaustive address book. Frequent (favored) correspondents could be highlighted by me for ease in sending a new e-mail, and also to provide importance hints to the program. This is where I might say who my boss/wife/mother is.
A body of a (or more) specific e-mail being read, written, or old e-mail (sent or received) being reviewed.
And I could go on, but I won't. If anyone wants to write such a thing and wants to hear more, send me an, um, e-mail.
-kb, the Kent who has been saving all his e-mail (including spam!) for a year or so, providing plenty of raw material to test any such program.
Please check out:
http://homepage.mac.com/zoe_info/
Zoe is way ahead of this curve.
Phorecast downloads all your email into a database of your choosing; it is database abstracted using PHP's PEAR DB library.
.tsv translation file for any language you like. Version 0.5 (on the way) improves these functions, and adds a todo list as well.
Phorecast is a web application written in PHP that combines email, calendar, and address book functions. It is language abstracted, so you can write a
Full disclosure: I wrote it, and I use it as my primary email client.
Try out Phorecast, open-source email, calendar,
Really, the diagrams help convey many of the points, but do the equations really tell you anything? Can anyone actually read those and explain them?
If I didn't know better, I'd think these sorts of papers ( which are common ) were a cheap attempt to sneak obvious claims past the patent office. I guess it's this sort stuff that got the patent office in the trouble it has seen.
Well, the attentive reader would have noted that I pointed out that Adobe wanted a very high per-seat license. Apple wanted to pay a flat rate, IIRC, and the two companies didn't work it out. So Apple went a different way.
DPS was used in a more fundamental way in NEXTSTEP. It was really amazing. There was true WYSIWYG, as the code on the screen was what was literally sent to the printer. Layout was really improved as a result, and you could mix postscript code with your drawing program efforts and see it previewed in a live fashion on-screen. It was easy to save documents in a portable fashion (PS), and a dozen other things.
There should be a moratorium on the use of the apostrophe.
Max V.
NeXTMail/MIME Mail welcome
How about converting to html?
This may also be a reverse DNS resolution problem. Check that your IP resolves to your hostname and that your hostname resolves to your IP. If not, some sendmail installations will reject your mail. Also, make sure your sendmail is sending out the correct hostname - eg, you can set up your machine so that it thinks its hostname is something.domain.com instead of some-long-crap-dsl-023-094.domain.com where something.domain.com is not an actual DNS record. This works fine for everything except when sendmail starts sending out emails claiming something.domain.com as originator.
Another thing you can do is configure sendmail to send all mail addressed to "user+any_arbitrary_string@domain.com" to "user@domain.com". This is useful since I don't have to do anything to generate a new email address. Search google.
I'll add that giving out a separate email addy for every company works beautifully. It also lets you know when some company sells your email address, something they will never admit to doing otherwise. I now get zero spam in my inbox.
The main result in Kleinberg's paper relates to finding NEW topics that start to appear in the stream. Let's say you already have categorization filters (procmail, keyword filters, your own set of folder hierarchies, whatever...), but there's a new topic that starts showing up in your mail, or in your newsgroup feed, or on CNN. Klienberg's result is a way to find that the new stuff really is NEW, and you might want to group it up together, and make a folder for it. You could do that automatically, or by hand, but first you have to know that there's a topic.
there's a bunch of other work in this area, what the NLP types call TDT -- "Topic Detection and Tracking"
Check out sneakemail.com - it does basically this, but at their domain name, and you can set filters of particular addresses, or just delete them. Very useful idea, I'd definitely be willing to pay for it though...
jzw of Mozilla/Netscape fame have a hypothetical program called Intertwingle which is (Score:5,Interesting) ....
RFC1925
There's been lots of work on auto-classifying email. I did my semester project in Machine Learning on this in 1999. It's a fairly simple study, but it seems like a Naive Bayesian classifier using word counts as features does a pretty decent job of classifying email, and does really well on spam.
The paper is here here.
J.
who the hell gets so much email they need to
mine for text, christ ??!! dont change your email filtering, change your pathetic life !!
there are plenty of other things far more worth mining than TEXT
As much as slashdotters hate lawyers...
And most politicians...
Maybe we should learn how to use them...
Use the laws in place. Sue them for the costs associated with spam. Sue them when they break the laws that exist to protect consumers. Whether it is spam, telemarketers, or Best Buys. Stiff it to them. Out smart them. After all, arent we geeks and nerds? By the world's definition arent we all supposed to be smarter, or a step above average person?
----- LoboSoft specializes in Digital Language Lab
Here
/cj
www.80-20.com (I think)
Integrates with Outlook (not UNIX version). But it offers real-time indexing of email, contacts, local and networked files. Super cheap for what you get.
It's saved my butt a hundred times when I can only remeber a fragment of someone's contact info, message or whatever.
They're the worst marketers in the world. They owe me for this one!
http://www.hiredinsight.com
i'm taking a class with kleinberg right now and he's a great lecturer. if anyone is interested in algorithms of any kind, go read his papers.
Reminds me of the maps for the 3D network game for the Mac that Ambrosia made...Avara, I think? The maps were vector graphics, where different shapes meant different things and text inside the shapes was code. Very cool idea. I think there's still a lot of potential in the idea that source code doesn't necessarily need to be a simple linear text file.
Karma: Good (despite my invention of the Karma: sig)
Aha, is this why it works at work (where my hostname is correct and resolvable), but not at home with my ISP, where my hostname remains the same but could not be looked up?
I just dial of over a modem, and its possible I configured that kind of perculiarly, because of wanting to switch between the LAN at work and my dialup at home.
Haha, that is what I like to see. Some common sense once in a while.
Some other transgressions: the Mac OS has forced the Apple menu on its users for nearly 20 years. Why can't I have a 3rd party menu? And sure people could download an alternative to GNOME terminal, but realistically who will exert the effort? And why don't I have a choice of who provides me with a tea timer in KDE?
Karma: Good (despite my invention of the Karma: sig)
There are plenty of e-mail mining tools in development. This particular work takes one particular approach to mining the data. Whether this approach will turn out to be useful remains to be seen.
this is perhaps the greatest example of slashdotter myopia ever. I don't give a crap about my karma, I just have to laugh at this AC:
It shouldn't take two months to get ghostscript and ghostview. In fact, it comes with most modern operating systems.
Clue time: 99% of people who've ever used a computer have never heard of either. If they click on the link above, they get a windows file box for "open with" and they wonder why the author didn't inlude a warning of what this strange file format was and what, exactly, they are supposed to do with this file.
DO NOT DISTURB THE SE
I also have my own domain name but I'm limited to 5 forwarded email addresses. I wanted to do what you suggested a while ago but couldn't. Then I stumbled across Sneakemail and it basically did everything I had intended anyway.
In a nutshell, you sign up for an account, giving only a contact email address (I use spam AT threewordslong DOTTY com). Once logged in you can create a new, randomized email address for each new web service that needs an email address. If one of these services spams or sells your sneakemail address you: a) know exactly who did it and cease further business with them and b) can filter on that specific email address.
It's a great service and no, I don't work for them...
"Where is the wisdom we have lost in knowledge, and where is the knowledge we have lost in information?"-T.S.Eliot
Well if they dont know what a postscript file is, they aren't going to be able to provide much of an objective review of a reasearch paper either.
158213 Apr 19 09:41 bhs.ps.bz2
t.
There are several articles on /. concerning lawsuits against spammers.
i ng &op=stories&author=&topic=111§ion=&sort=1
http://slashdot.org/search.pl?query=sue+sued+su
A fool throws a stone into a well and a thousand sages can not remove it.
The rogue marketers will just let another company entity send th enext spam.
Ie. starta a new throw-away company each time they want to spam us.
Qmail is good for this sort of thing. By default, a user receives everything at username-*@domain.com.
.qmail-amazon and .qmail-slashdot files in your home directory and have a .qmail catch-all.
So, I subscribe to amazon with username-amazon@domain.com, slashdot with username-slashdot@domain.com etc.
You can then control the delivery location of mails to these recipients using
This comes in handy for filing mailing-lists away, filtering out spam etc. Its also interesting to see who's sold you down the river to spammers, I recently started receiving spam to username-bsdtoday@domain.com... bastards!
Cheers,
Si
I could list it all here, but it's much more efficient to just point people at:
http://www.iarchitect.com/lotus.htm
(Which is a site that everyone should read before doing UI stuff.)
Sample of one of the "best" bits:
Judging from the number of visitors who have mentioned it, the process of copying messages in Notes is perhaps its worst interface "feature". Apparently, when mail messages are copied from one folder to another, the message itself is not copied; Notes creates a "reference" to the message. Unbeknownst to the user, if you delete the reference, Notes will in turn delete the message itself. Similarly, deleting the message will cause all references to it to also be deleted.
I'd like to find something like this - where
as I browse across a web page I could active
a program that would look at the page, and suggest a series of folders that appear to be relevant.
If I agree, I click okay and go on. If I think a category is unnecessary, or missing, I would
have the option of adding a category.
I see this as a parallel need to the mining
of the email.
URL: http://xanga.com/lvirden > Quote: Saving the world before bedtime. Even if explicitly stated to the contrary, n
SWISH++ (my search engine) specifically knows to index mail/news files (including text, HTML, RTF, LaTeX files) and attachments of any of those (in quoted-printable or base64 encodings). It can also index any other kind of attachment via external filter programs. A procmail recipe for auto-splitting incoming mail is included in the distro. I also believe that my statement of SWISH++ being the fastest open-source indexer is accurate.
If you reply, do so only to what I explicitly wrote. If I didn't write it, don't assume or infer it.
Yeah sure, embed it in the OS. More proof that any notion of what constitutes an "Operating System" has been completely destroyed by Microsoft's marketing department.
Dude, it's real simple. Install ghostview, set up as helper app in the browser of your choice for application/postscript.
Bundle with the OS. Feh!
Didn't NeXT OS do this?
IIRC, postscript was the underlying graphics transport for screens, so they had WYSIWYG everywhere.
SpamBouncer is a set of procmail recipes to filter spam.